NOC 2022 初中组选择题和编程题题解

注意：本文有几个问题：

部分题目我也不确定答案，而且我水平不行，有些题目我还真不会，大家就把我的答案当个参考吧。

目前有一大半的题目因为作者比较懒，暂时没写，空在那儿，可以下载原题自己做做。

1 初中组选拔赛

原题链接，提取码：efy6。

1.1 选择题部分

1.1.1 A。C++ 中，main() 函数有且仅有一个。

1.1.2 D。A 选项 \((42.8)_{16}=(66.5)_{10}\)，B 选项 \((66.5)_{10}\)，C 选项 \((1024.8)_{8}=(66.5)_{10}\)，D 选项 \((1000011.1)_{2}=(67.5)_{10}\)。

1.1.3 D。C++ 中 if (expression) 里的 expression，只要不是 0 就是真，所以 A、B 和 C 都是等价的，只有 D 不一样。

1.1.4 A。这道题目要反过来思考，问有多少个含有 2 的数字，那就算出有多少个不含 2 的数字。1 到 2000 之间，共有 \(9*9*9*2-1=1457\) 个不含 2 的数字（减去 1 是因为多了一个 0），那就有 \(2000-1457=543\) 个含有 2 的数字，再加上都含有 2 的 2001 到 2022，有 22 个数字，总共 565 个。

1.1.5 A。C 和 D 肯定不用多说，B 因为 C++ 里从左向右计算，++ 晚于 * 运算，所以结果依然是 4。A 选项中，++ 早于 *，结果是 6。

1.1.6 B。做个简单的计算就可以发现，第 n 次循环的结果就是 \(2^{n}-1\)，因此第 50 次循环的结果就是 \(2^{50}-1\)。

1.1.7 B。做个模拟，就能发现 B 的顺序是没办法实现的。

1.1.8 C。自行查找各种排序算法的时间复杂度表格。

1.1.9 A。牢记 C++ 的数组下标是从 0 开始的，所以该值之前的行数就是 i，列数就是 j,结果也就是 \(i*n+j\)。

1.1.10 C。这个我真的不知道了，到网上查了一圈也没有结果，就蒙了一个，有懂的同学请留言指教。

1.1.11 C。这道读程很简单了，cnta 就是字符串里英文字母的数量，cntn 就是数字的数量，getline() 可以读入空格，所以 D 是正确的，但是可能还有其他特殊字符，所以 cnta + cntn 不一定是总字符数。

1.1.12 D。这个程序先读入一个字符串，然后统计里面各个字符的输入次数，输出字典序第一个只出现了一次的字符，如果没有，就输出 no。那么很明显了，它一不会输出个数，二不会输出多个，至于 B 的情况更不可能，只有 D 正确。

1.1.13 B。递归函数，数据比较小，手动模拟即可。最终会形成一棵二叉树，关键是找到遍历的顺序（先序遍历），按序输出就行。大致如图，结点右边括号里的数字是顺序，连接线旁边的是返回结果。最后别忘了还有个返回值输出。

                     6(1)     --- 最终结果：3
                    2/  \1
                  3(2)  2(5)
                 1/  \1
                1(3) 0(4)

（我尽力了，唉。）

1.1.14 A。这道题循环判断，分别将每一个数和所有数一次比较，如果前者小于后者，或者前后相等且前者下标比较大，就给计数器 cnt 加一。很容易发现，因为所有数据都是相等的，所以每次结果都是 i - 1，当 cnt == m 时，也就是 \(i-1=m\)，\(i=m+1\)。

1.1.15 这道题目和上面那题的程序是一样的，但是给的样例变成了升序且不相等。这时候 cnt 加一的条件就变成前一个了，这回 cnt 的结果就成了 n - m，也就是 \(i=n-m\)。

1.2 编程题部分

1.1.16 第一道打卡题，相当简单，不仔细说了，自行查看代码即可。

#include <iostream>

using namespace std;
int stepMove;
string secretStr;

int main() {
    cin >> stepMove >> secretStr;
    stepMove = stepMove % 26;
    char tmpRes;
    for (int i = 0; i < secretStr.length(); i++) {
        tmpRes = secretStr[i] - stepMove;
        if (secretStr[i] >= 'A' && tmpRes < 'A') {
            tmpRes = 'Z'- ('A' - tmpRes);
        }
        if (secretStr[i] >= 'a' && tmpRes < 'a') {
            tmpRes = 'z'- ('a' - tmpRes);
        }
        cout << tmpRes;
    }
}

1.1.17 这道题目粗略估算 \(O(n^{3})\) 勉强能过，所以就用了暴力解法加上一点点优化，希望能拿到大部分分。这个程序就仅供参考了。

#include <iostream>

using namespace std;
int matches;
int students;
int matchResult[1200][1200];
int rankList[1200][1200];
int beKilled[1200];
int killedCnt;

int main() {
    cin >> matches >> students;
    for (int i = 1 ; i <= matches; i++) {
        for (int j = 1 ; j <= students; j++) {
            cin >> matchResult[i][j];
            rankList[matchResult[i][j]][i] = j;
        }
    }
    bool keepWin;
    for (int i = 1; i <= students; i++) {
        for (int j = 1; j <= students; j++) {
            if (i == j) {
                continue;
            }
            if(beKilled[i] == j) {
                break;
            }
            keepWin = true;
            for (int k = 1; k <= matches; k++) {
                if (rankList[i][k] > rankList[j][k]) {
                    keepWin = false;
                    break;
                }
            }
            if (keepWin) {
                killedCnt++;
                beKilled[j] = i;
            }
        }
    }
    cout << killedCnt;
    return 0;
}

1.1.19 TBC...

1.1.20 TBC...