|
今天，胖頭魚老師要為大家?guī)硪环軨SP-J組的詳細(xì)解題報(bào)告。 其中展現(xiàn)的是胖頭魚老師親臨考場(chǎng)時(shí)的（緊張）思維。 一、單項(xiàng)選擇題 考察域名常識(shí)。 中國(guó)的頂級(jí)域名是.cn，china的縮寫。 考察二進(jìn)制位運(yùn)算。 將兩個(gè)二進(jìn)制表示的數(shù)對(duì)齊以后逐位作邏輯運(yùn)算，與運(yùn)算是兩個(gè)數(shù)都為1時(shí)結(jié)果為1，否則為0，最后得到答案01 0010 1000 0011。 考察二進(jìn)制位的計(jì)數(shù)單位。 一個(gè)字節(jié)占8位，所以32位整數(shù)占4個(gè)字節(jié)。 考察程序的三大結(jié)構(gòu)，循環(huán)結(jié)構(gòu)中的for語句。
循環(huán)從1到c一共是c次，每一次s都會(huì)-1，所以一共是-c，結(jié)果為a - c。 考察二分算法。 折半查找每次可以將查找范圍減半，2^7 = 128 > 100，所以需要7次查找。 也可以根據(jù)查找范圍一個(gè)個(gè)數(shù)，50、25、12、6、3、1、0，7次查找后查找范圍為0。 考察數(shù)據(jù)結(jié)構(gòu)鏈表的特性。 鏈表只記錄前一個(gè)元素和后一個(gè)元素，所以可以根據(jù)需要來分配空間，插入、刪除的時(shí)候也不存在移動(dòng)這個(gè)說法。 但是不能像數(shù)組一樣支持隨機(jī)訪問。 考察組合數(shù)學(xué)，或者枚舉算法。
球和袋子都是相同的，所以只考慮裝入袋子的球的數(shù)量，并且裝的時(shí)候每個(gè)袋子中球的數(shù)量是不減的。 組合數(shù)學(xué)苦手的同學(xué)可以扳指頭數(shù)，只用數(shù)4個(gè)袋子就行了，一共18種。 袋子 1 2 3 4 方案數(shù) 0 0 0 0~4 5 0 0 1 1~3 3 0 0 2 2~3 2 0 1 1 1~3 3 0 1 2 2 1 0 2 2 2 1 1 1 1 1~2 2 1 1 2 2 1 考察數(shù)據(jù)結(jié)構(gòu)二叉樹的存儲(chǔ)。
題目中其實(shí)已經(jīng)提示了編號(hào)的方式，所以沒學(xué)過二叉樹也沒關(guān)系。 根據(jù)圖可以計(jì)算出每個(gè)節(jié)點(diǎn)的編號(hào)，其中右下角的等于15，是最大的 。 考察數(shù)學(xué)，素?cái)?shù)判斷。 不熟悉100以內(nèi)素?cái)?shù)的同學(xué)可以逐個(gè)試除一下，得到97。 考察數(shù)學(xué)，約數(shù)判斷和求公約數(shù)。
377 - 319 = 58，答案就很明顯了是29的倍數(shù)。 考察貪心算法，或者枚舉算法。 可以優(yōu)先嘗試跑性價(jià)比高的一小時(shí)方案，發(fā)現(xiàn)正好跑3次一小時(shí)再加2次半小時(shí)可以達(dá)到21公里，然后算出消耗了2400卡。 考察數(shù)學(xué)，抽屜原理。
一共有4種花色的牌，抽13張，每種花色都有3張時(shí)還多出1張，所以至少有4張牌花色相同。 考察組合數(shù)學(xué)。
五位數(shù)的中間位顛倒以后還是中間位，所以只能填寫0、1、8，第1位和第2位顛倒以后確定了第4位和第5位，分別可以填寫0、1、8、6、9。 所以一共是3 * 5 * 5 = 75種。 考察數(shù)據(jù)結(jié)構(gòu)，二叉樹的遍歷。 根據(jù)中序遍歷和后序遍歷的特性，可以畫出圖，得到前序遍歷為ABDEGHJCFI。 
考察計(jì)算機(jī)常識(shí)。
圖靈是計(jì)算機(jī)領(lǐng)域的人物。
二、閱讀程序
程序大意：對(duì)于字符串中的第i位，如果i是n的約數(shù)，并且第i個(gè)字符比'a'(97)要大，就減少'a'(97)-'A'(65)。 #include <cstdio>#include <cstring>using namespace std;char st[100];int main() { scanf('%s', st); int n = strlen(st); // 計(jì)算字符串的長(zhǎng)度 for (int i = 1; i <= n; ++i) { // 對(duì)字符串中的第i個(gè)字符進(jìn)行循環(huán)枚舉 if (n % i == 0) { // 判斷i是否是n的約數(shù) char c = st[i - 1]; // 取出字符串中的第i個(gè)字符 if (c >= 'a') // 判斷字符是否大于97 st[i - 1] = c - 'a' + 'A'; // 將字符減少32 } } printf('%s', st); // 輸出字符串 return 0;}
1）考察程序的輸入輸出。 程序中沒有對(duì)字符串中的字符范圍進(jìn)行任何要求。 2）考察表達(dá)式運(yùn)算，除法和取模。 如果i = 0，那么在n對(duì)i進(jìn)行取模運(yùn)算時(shí)就會(huì)報(bào)錯(cuò)，因?yàn)槌?了。 3）考察約數(shù)判斷，注意不是素?cái)?shù)判定。 判斷素?cái)?shù)的時(shí)候通常用這種方式進(jìn)行加速，是因?yàn)閟qrt(n)之后的約數(shù)與之前的約數(shù)是一一對(duì)應(yīng)的，這也就說明了sqrt(n)之后還有約數(shù)。 如果將循環(huán)范圍縮小了，就不會(huì)處理后面的約數(shù)，導(dǎo)致答案不一樣。 4）考察數(shù)據(jù)類型，字符型的存儲(chǔ)與表示。 大寫字母的ASCII碼都要小于'a'(97)，所以不會(huì)對(duì)字符串進(jìn)行修改。 5）考察數(shù)學(xué)，約數(shù)數(shù)量計(jì)算。 將要計(jì)算的數(shù)分解質(zhì)因數(shù)，每個(gè)質(zhì)因數(shù)的出現(xiàn)次數(shù)加1，再乘起來就是約數(shù)個(gè)數(shù)。 最多時(shí)每個(gè)約數(shù)的位置都可以修改，18有6個(gè)約數(shù)。 6）考察數(shù)學(xué)，約數(shù)數(shù)量計(jì)算。 10000 = 2^5 * 5^5，一共有(5 + 1) * (5 + 1) = 36個(gè)約數(shù)。 不會(huì)求約數(shù)個(gè)數(shù)的同學(xué)可以暴力算一下其他幾個(gè)數(shù)的約數(shù)個(gè)數(shù)，用排除法也能得到這個(gè)答案。 程序大意：有ab兩組元素，兩組元素之間可以兩兩配對(duì)（0可以任意次配對(duì)）。 初始時(shí)所有元素都和另一組的0配對(duì)，每次考察a組的第x個(gè)元素和b組的第y個(gè)元素，如果這兩個(gè)元素之前的配對(duì)交叉了，則把它們之前的配對(duì)元素都重新配對(duì)到0，并將這兩個(gè)元素配對(duì)。 最后求有多少個(gè)元素和0配對(duì)。 
#include <cstdio>using namespace std;int n, m;int a[100], b[100];
int main() { scanf('%d%d', &n, &m); // n個(gè)數(shù)與m次操作 for (int i = 1; i <= n; ++i) // 初始時(shí)所有數(shù)都跟0配對(duì) a[i] = b[i] = 0; for (int i = 1; i <= m; ++i) { int x, y; scanf('%d%d', &x, &y); if (a[x] < y && b[y] < x) { // 對(duì)于想要配對(duì)的數(shù)，判斷原先的一對(duì)配對(duì)是否交叉 if (a[x] > 0) // 將原先的配對(duì)元素重新和0配對(duì) b[a[x]] = 0; if (b[y] > 0) a[b[y]] = 0; a[x] = y; // 當(dāng)前兩個(gè)元素建立新的配對(duì) a[y] = x; } } int ans = 0; for (int i = 1; i <= n; ++i) { // 統(tǒng)計(jì)和0配對(duì)的元素?cái)?shù)量 if (a[i] == 0) ++ans; if (b[i] == 0) ++ans; } printf('%d\n', ans); return 0;}
1）考察對(duì)程序含義的理解。 m > 0時(shí)一定會(huì)有一個(gè)配對(duì)，所以和0配對(duì)的元素的數(shù)量一定小于2n。 2）考察對(duì)程序含義的理解，反例設(shè)計(jì)。 統(tǒng)計(jì)是按照元素編號(hào)的順序進(jìn)行的，如果有一個(gè)x < y的配對(duì)，那么統(tǒng)計(jì)完b中的第x個(gè)元素時(shí)ans會(huì)變成奇數(shù)。 3）考察對(duì)程序含義的理解，反例設(shè)計(jì)。 如果ab中的第i個(gè)元素進(jìn)行配對(duì)，則a[i]和b[i]同時(shí)>0。 4）考察對(duì)程序含義的理解，反例設(shè)計(jì)。 x總是小于y不代表x之前沒有別的配對(duì)，如果x之前有別的配對(duì)，則照樣會(huì)執(zhí)行清理。 可以依次對(duì)(1, 1)和(1, 2)進(jìn)行配對(duì)，則第二次操作時(shí)會(huì)對(duì)1的配對(duì)進(jìn)行清理。 5）考察對(duì)程序含義的理解。 x和y兩兩不同時(shí)，每次都會(huì)成功進(jìn)行配對(duì)，m次會(huì)產(chǎn)生m對(duì)配對(duì)，所以和0配對(duì)的元素?cái)?shù)量為2n - 2m。 6）考察對(duì)程序含義的理解。 x各不相同，y每次相等，那么x和y配對(duì)時(shí)每次都會(huì)清理掉之前的配對(duì)，最終只會(huì)產(chǎn)生一組配對(duì)，所以和0配對(duì)的元素?cái)?shù)量為2n - 2。 程序大意：將一個(gè)元素序列根據(jù)a值構(gòu)造成一棵二叉樹，每次在序列中選擇a值最小且最靠前的元素作為根，根之前的序列構(gòu)建左子樹，根之后的序列構(gòu)建右子樹。 最后求出每個(gè)節(jié)點(diǎn)的深度乘以b值的和。 #include <iostream>using namespace std;const int maxn = 10000;int n;int a[maxn];int b[maxn];int f(int l, int r, int depth) { // 計(jì)算序列中l(wèi)到r這幾個(gè)元素構(gòu)成的根深度為depth的子樹的權(quán)值 if (l > r) // 判斷空子樹 return 0; int min = maxn, mink; for (int i = l; i <= r; ++i) { // 查找a值最小的最靠左的元素 if (min > a[i]) { min = a[i]; // 記錄最小值 mink = i; // 記錄位置 } } int lres = f(l, mink - 1, depth + 1); // 計(jì)算左子樹 int rres = f(mink + 1, r, depth + 1); // 計(jì)算右子樹 return lres + rres + depth * b[mink]; // 當(dāng)前子樹的權(quán)值為左右子樹權(quán)值與根權(quán)值的和}int main() { cin >> n; for (int i = 0; i < n; ++i) // 讀入每個(gè)元素的a值 cin >> a[i]; for (int i = 0; i < n; ++i) // 讀入每個(gè)元素的b值 cin >> b[i]; cout << f(0, n - 1, 1) << endl; // 構(gòu)建子樹并計(jì)算權(quán)值 return 0;}
1）考察循環(huán)遍歷數(shù)組，也可以直接進(jìn)行反例設(shè)計(jì)。 重復(fù)的a值不影響查找最小元素，所以不會(huì)出錯(cuò)。 2）考察對(duì)程序含義的理解。 所有元素的b值為0，則權(quán)重也全部為0，總權(quán)重就是0。 可以根據(jù)程序觀察一下，所有的計(jì)算都會(huì)和b值進(jìn)行相乘，沒有常數(shù)，也可以猜到結(jié)果為0。 3）考察數(shù)據(jù)結(jié)構(gòu)二叉樹，節(jié)點(diǎn)分層時(shí)的特性，最劣極端情況。 每個(gè)子樹中的每個(gè)節(jié)點(diǎn)都會(huì)進(jìn)行一次比較，最壞情況下二叉樹有n層（每次只劃分出一個(gè)子樹），所以比較次數(shù)為100 + 99 + ... + 1 = 5050，與5000最接近。 4）考察數(shù)據(jù)結(jié)構(gòu)二叉樹，節(jié)點(diǎn)分層時(shí)的特性，最優(yōu)極端情況。 最少情況下二叉樹有l(wèi)og層，100個(gè)節(jié)點(diǎn)約為7層，每一層的總節(jié)點(diǎn)數(shù)估算為n，則比較次數(shù)大約為700次，與600最接近。 5）綜合考察對(duì)程序含義的理解、二叉樹的結(jié)構(gòu)與數(shù)學(xué)計(jì)算。 為了讓輸出最大，則需要讓b值大的元素深度盡可能的大，一條鏈可以達(dá)成這個(gè)要求，則權(quán)值為1^2 + 2^2 + ... + 10^2 = 385。 6）綜合考察對(duì)程序含義的理解、二叉樹的結(jié)構(gòu)與數(shù)學(xué)計(jì)算。 每個(gè)元素的b值均為1，則計(jì)算的是元素的深度和，所以需要讓二叉樹的深度盡可能小。 那么第一層可以有1個(gè)節(jié)點(diǎn)，第二層可以有2個(gè)，第三層可以有4個(gè)，以此類推。權(quán)值為1 * 1 + 2 * 2 + 4 * 3 + 8 * 4 + ... + 32 * 6 + 37 * 7 = 580，注意最后一層節(jié)點(diǎn)數(shù)不滿。
三、完善程序 程序思路：考察分治算法，通過遞歸的方式來對(duì)矩陣進(jìn)行填充。 從0作為元開始，每次將當(dāng)前的矩陣劃分成四個(gè)子矩陣，對(duì)應(yīng)了一次變換，并根據(jù)變化規(guī)則分別得到四個(gè)子矩陣的元。 子矩陣用遞歸的方式進(jìn)行填充，直到不再變換。 #include <cstdio>using namespace std;int n;const int max_size = 1 << 10;
int res[max_size][max_size]; // 01矩陣
void recursive(int x, int y, int n, int t) { // 填充左上角為(x, y)的n階子矩陣，且元為t if (n == 0) { // 0階矩陣只有一個(gè)數(shù) res[x][y] = t; // 等于元，不再變換 return; } int step = 1 << (n - 1); // 分成的子矩陣之間的距離 recursive(x, y, n - 1, t); // 左上角的子矩陣，元不變 recursive(x, y + step, n - 1, t); // 右上角的子矩陣，元不變 recursive(x + step, y, n - 1, t); // 左下角哦的子矩陣，元不變 recursive(x + step, y + step, n - 1, !t); // 右下角的子矩陣，元取反}
int main() { scanf('%d', &n); recursive(0, 0, n, 0); // 初始時(shí)要填充左上角為(0, 0)的n階子矩陣，初始時(shí)元為0 int size = 1 << n; // n階矩陣的寬度為2^n for (int i = 0; i < size; ++i) { for (int j = 0; j < size; ++j) printf('%d', res[i][j]); puts(''); } return 0;}
下面講解一下對(duì)于不能完全看懂程序的同學(xué)該如何選擇。 1）如果填寫一個(gè)常數(shù)，那整個(gè)矩陣就是常數(shù)矩陣了。 而且這個(gè)t在函數(shù)中傳遞下來就只有這里可以直接使用，其他地方都是參數(shù)。 所以除了t也沒別的選擇。 2）分成四個(gè)子矩陣，看不懂程序的根據(jù)另外兩行都能猜出來。 另外兩行中可以發(fā)現(xiàn)，x和y分別有加與不加兩種可能，組合起來正好四種可能，所以肯定沒減號(hào)。 3）同上。 4）通過函數(shù)中的參數(shù)命名可以猜出肯定是n了。 然后測(cè)一下n = 1就可以確定第二個(gè)參數(shù)填0。 5）測(cè)一下n = 1就知道肯定是1 << n。 程序思路：就是計(jì)數(shù)排序，和桶排序的原理有些相似。 核心思想是，先統(tǒng)計(jì)每個(gè)值x出現(xiàn)的次數(shù)，再計(jì)算出小于等于每個(gè)值x的元素?cái)?shù)量t，這個(gè)數(shù)量t決定了排序時(shí)值為x的元素應(yīng)該從第t大開始逐個(gè)往前排，這樣就完成了單關(guān)鍵字排序。 雙關(guān)鍵字排序時(shí)，要先排第二關(guān)鍵字，讓元素都是根據(jù)第二關(guān)鍵字有序的。然后根據(jù)第一關(guān)鍵字重新排序時(shí)，首先可以保證結(jié)果是第一關(guān)鍵字有序的，同時(shí)對(duì)于第一關(guān)鍵字相同的元素，它們已經(jīng)按照第二關(guān)鍵字排好序了，所以最后的結(jié)果是雙關(guān)鍵字排序。 #include <cstdio>#include <cstring>using namespace std;const int maxn = 10000000;const int maxs = 10000;
int n;unsigned a[maxn], b[maxn], res[maxn], ord[maxn];unsigned cnt[maxs + 1];
int main() { scanf('%d', &n); for (int i = 0; i < n; ++i) scanf('%d%d', &a[i], &b[i]); memset(cnt, 0 , sizeof(cnt)); // 清0統(tǒng)計(jì)數(shù)組 for (int i = 0; i < n; ++i) ++cnt[b[i]]; // 先對(duì)第二關(guān)鍵字排序，統(tǒng)計(jì)每個(gè)b值的數(shù)量 for (int i = 0; i < maxs; ++i) cnt[i + 1] += cnt[i]; // 累計(jì)小于等于每個(gè)b值的元素?cái)?shù)量 for (int i = 0; i < n; ++i) ord[--cnt[b[i]]] = i; // 根據(jù)第i個(gè)元素的b值，按照計(jì)算出的數(shù)量開始右后往前排列 memset(cnt, 0 , sizeof(cnt)); for (int i = 0; i < maxs; ++i) ++cnt[a[i]]; // 接下來對(duì)第一關(guān)鍵字排序，統(tǒng)計(jì)每個(gè)a值的數(shù)量 for (int i = 0; i < maxs; ++i) cnt[i + 1] += cnt[i]; // 累計(jì)小于等于每個(gè)a值的元素?cái)?shù)量 for (int i = n - 1; i >= 0; --i) // 因?yàn)榕判蛑兄迪嗤脑厥菑暮笸胺诺模藭r(shí)元素已經(jīng)按b值排好序了，所以要從后往前來放元素才能保證a值相同的元素b值是由小到大的 res[--cnt[a[ord[i]]]] = ord[i]; // 之前排好序的元素編號(hào)在ord中，要按照第二關(guān)鍵字排序來放 for (int i = 0; i < n; ++i) printf('%d %d\n', a[res[i]], b[res[i]]); // 雙關(guān)鍵字排序的結(jié)果在res中 return 0;}
下面講解一下對(duì)于不能完全看懂程序的同學(xué)該如何選擇。 1）先排第二關(guān)鍵字，肯定要選只有b[i]的選項(xiàng)。 2）按照第二關(guān)鍵字排序，答案肯定跟b[i]相關(guān)。 每個(gè)元素有ab兩個(gè)值，ord中只能記錄元素編號(hào)，所以肯定是保存i。 3）現(xiàn)在根據(jù)第一關(guān)鍵字排序，答案應(yīng)該是跟a[i]有關(guān)。 有個(gè)與a[i]和b[i]同時(shí)有關(guān)的選項(xiàng)明顯越界了，肯定不可能。 4) ord里面存的是元素編號(hào)，肯定不能跟a[i]配合使用，而是要跟a[ord[i]]配合使用。 同時(shí)這是根據(jù)第一關(guān)鍵字排序，應(yīng)該是與a有關(guān)。 5）res和ord里面存的都是元素編號(hào)，肯定不能嵌套使用。 答案要按照排序輸出，肯定與res或者ord有關(guān)。
總體來說，題目還是出的挺好的，考察的知識(shí)點(diǎn)也比較全面，注重考察原理。 對(duì)于無法將知識(shí)點(diǎn)理解透徹的同學(xué)，也要學(xué)會(huì)根據(jù)上下文的線索來推導(dǎo)的能力，可以在選擇題的考試中爭(zhēng)取更多的分?jǐn)?shù)。 逐月
https://www. （請(qǐng)?jiān)谟?jì)算機(jī)上打開）
一個(gè)由中老年信息學(xué)愛好者傾情打造的網(wǎng)站
免費(fèi)提供各種信息學(xué)的學(xué)習(xí)資料
歡迎大家前來學(xué)習(xí)
|
