一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. 质因数分解是指将一个数字分成若干个质数的乘积。为了方便，如果质因数分解中出现了多个相同质因数，可以写成指数形式。下面（ ）是 2024 的质因数分解。

{{ select(1) }}

• $2^3\times 11\times 23$
• $2^4\times 127$
• $2^2\times 22\times 23$
• $7+2017$

2. CCF NOI 系列比赛中，选手源代码长度不得超过 $100\text{ KB}$。现有四位选手各写了一份代码，长度依次是 $2024$ 字节、$41\text{ MB}$、$0.04\text{ MB}$、$114514\text{ b}$。有（ ）个选手的代码没有超过长度限制。

{{ select(2) }}

• 1
• 2
• 3
• 4

3. 在 C++ 中，以 0 开头的数字字面量是八进制的，如 015 == 13。在 C++ 中计算 072 ^ 110 的结果是（ ）。

{{ select(3) }}

• 84
• 78
• 38
• 0

4. 若根的深度为 1，则拥有 2024 个结点，其中 921 个结点是叶子的二叉树深度最大是（ ）。

{{ select(4) }}

• 1102
• 1103
• 1104
• 不存在这样的二叉树

5. 临近 CSP，小 A 想从去年云斗学院的 CSP-J 模拟赛和 CSP-S 模拟赛中各挑一道题进行练习，但是希望它们不属于同一知识点。已知 CSP-J 模拟赛的四题知识点依次为模拟、数学、模拟、DP，而 CSP-S 模拟赛的四题知识点依次为模拟、DP、高斯消元、并查集，请问小 A 有多少种选法？（ ）

{{ select(5) }}

• 10
• 13
• 15
• 16

6. 计算后缀表达式 4 3 4 - - 6 2 / 1 * + 的结果是（ ）。

{{ select(6) }}

• 6
• 7
• 9
• 前三个选项都不对

7. 执行如下代码片段后，*i 的值是（ ）。

vector<int> a = {10, 20, 30, 40, 50};
auto i = a.end() - 3;

{{ select(7) }}

• 30
• 20
• 47
• 未定义行为

8. 下列函数实现了翻转字符串 $s$ 的第 $l\sim r$ 个字符的功能，例如 range_rev("1234567", 2, 5) 的结果是 1543267。空白处应填写（ ）。

string range_rev(string s, int l, int r) {
    for (int i = l - 1; i < (l + r) / 2; i++)
        swap(s[i], s[_______]);
    return s;
}

{{ select(8) }}

• l + r + 1 - i
• l + r - i
• l + r - 1 - i
• l + r - 2 - i

9. 一份文件仅含有英文小写字母，其中字母 $a,b,c,\ldots,z$ 出现次数依次为 $2^1,2^2,\ldots,2^{26}$。若使用二进制哈夫曼编码方式，则字母 $e$ 的编码长度是（ ）。

{{ select(9) }}

• 20
• 21
• 22
• 23

10. STL 是我们写代码的好帮手，下面关于 STL 的叙述中，正确的是（ ）。

{{ select(10) }}

• 若 a 是个 list<int>，那么 a[3] 可以求 a 的第四个元素。
• 若 a 是个 queue<int>，那么 a.top() 就是 a 的队首。
• reserve 函数可以用于反转一个序列。
• sort 函数填入适当的参数，就可以实现从大到小排序。

11. 如图所示的二叉树中，$A\sim J$ 分别代表一个 $0\sim 9$ 的自然数且不重复。已知该二叉树的前序遍历结果为 3192608574，则其中序遍历结果为（ ）。

{{ select(11) }}

• 9123547806
• 9215478063
• 9123605874
• 9123058746

12. 4 个男生和 3 个女生排成一列，要求存在至少一个女生排在至少一个男生前面，有（ ）种排法。

{{ select(12) }}

• 8640
• 5039
• 4896
• 144

13. 桌子上有背面朝上的 2、3、4、5、6、7、8 点扑克牌各一张，Bob 想要将这些牌从大到小排序，但是不能直接翻看这些牌。

每次 Bob 可以选一些牌交给 Alice，然后 Alice 可以指出这些牌中最大和最小的分别是哪张牌，并向 Bob 收费一元。请问 Bob 至少要花多少元才能将这些牌从小到大排序？（ ）

{{ select(13) }}

• 2
• 3
• 5
• 15

14. 现有一个 $3\times 3$ 的棋盘，每个格子写了一个自然数。你要从左上角走到右下角，每次只能向右或向下走一步，求经过的所有格子数字和最大值。

一同学采用贪心算法，每次从左上角开始，从右边和下面的格子中选出数值更大的格子然后走一步（若两个格子数值相等则随机选一个），直到到达终点。要想让这个算法必然出错，棋盘上这 9 个自然数中至多有（ ）个数为 0。

{{ select(14) }}

• 7
• 6
• 5
• 前三个选项都不对

15. 一张简单无向图有 100 个结点和 200 条边，下面三个情况中，不可能的有（ ）个。

(1) 有 20 个结点度数为 20。 (2) 有 40 个结点度数为 10。 (3) 有 90 个结点度数为 1。

{{ select(15) }}

• 0
• 1
• 2
• 3

二、阅读程序（判断题正确选“正确”，错误选“错误”；除特殊说明外，判断题 1.5 分，选择题 3 分；共 40 分）

第 1 题（第 16～21 题，共 12 分）

#include <iostream>
#include <cstdio>
using namespace std;

char code[26];
string key;
string s;

void encode()
{
    int len = s.length();
    for (int i = 0; i < len; i++)
        s[i] = code[((s[i] - 'a') + (key[i] - 'a')) % 26];
}

int main()
{
    for (int i = 0; i < 26; i++) code[i] = i + 'a';
    cin >> s >> key;
    encode();
    cout << s;
    return 0;
}

程序正常运行的含义是：程序正常退出且输出的字符串长度与 $s$ 相等。其他情况下为出错。假设输入的所有数据均为大写或小写字母，完成下列判断题和选择题。

16. 如果输入的字符串 $s$ 中有大写字母，那么程序一定会出错。

{{ select(16) }}

• 正确
• 错误

17. 如果输入的字符串 key 中有大写字母，那么程序可能会出错。

{{ select(17) }}

• 正确
• 错误

18. 正常情况下，输出结果一定全部为小写字母。

{{ select(18) }}

• 正确
• 错误

19. 为了保证程序正常运行，字符串 $s$ 和字符串 key 必须长度相等。

{{ select(19) }}

• 正确
• 错误

20. 当输入的字符串依次为 yundou 和 ccfcsp 时，输出结果为（ ）。

{{ select(20) }}

• awskfn
• awsfhj
• awsfgj
• awskgn

21. 若输入的 key 字符串为 yundou，输出的字符串为 rofgtw，那么输入的 $s$ 字符串为（ ）。

{{ select(21) }}

• tuskba
• tusdfc
• tuspkw
• tusthu

第 2 题（第 22～27 题，共 14 分）

#include <iostream>

const int mod = 29;
int n, t, m;
int prime[110], isprime[110], cnt;

void solve1(int n) {
    for (int i = 1; i <= mod; i++) {
        if (i * n % mod == 1) {
            std::cout << i << std::endl;
            return;
        }
    }
    std::cout << -1 << std::endl;
}

void solve2(int n, int m) {
    while (n != m) {
        if (n < m) {
            std::swap(n, m);
        }
        n -= m;
    }
    std::cout << n << std::endl;
}

void solve3(int n) {
    for (int i = 2; i <= n; i++) {
        if (!isprime[i]) {
            prime[++cnt] = i;
        }
        for (int j = 1; j <= cnt; j++) {
            if (i * prime[j] > n) {
                break;
            }
            isprime[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
    std::cout << cnt << std::endl;
}

int main() {
    std::cin >> t;
    if (t == 1) {
        std::cin >> n;
        solve1(n);
    } else if (t == 2) {
        std::cin >> n >> m;
        solve2(n, m);
    } else if (t == 3) {
        std::cin >> n;
        solve3(n);
    }
    return 0;
}

程序满足输入 $1\le t\le 3$，$1\le m,n\le 100$，且 $n$ 不为 29 的倍数。

22. 当 $t=1$ 时，有可能输出 $-1$。

{{ select(22) }}

• 正确
• 错误

23.（2 分）将第 18 行的 n != m 改为 n && m，同时将第 24 行的 std::cout << n << std::endl; 改为 std::cout << m << std::endl; 之后，结果不变。

{{ select(23) }}

• 正确
• 错误

24. 删除代码的第 37 行到第 39 行后，程序的输出依旧保持不变。

{{ select(24) }}

• 正确
• 错误

25. 当输入为 1 27 时，输出为（ ）。

{{ select(25) }}

• 18
• 14
• 27
• 24

26. 当 $t=2$ 时，程序所求的结果为（ ）。

{{ select(26) }}

• 最大公约数
• 最小公倍数
• 任意公约数
• 任意公倍数

27. 当输入为 2 78 52 时，输出为（ ）。

{{ select(27) }}

• 2
• 13
• 3
• 26

第 3 题（第 28～33 题，共 14 分）

#include <cstring>
#include <iostream>
using namespace std;
#define int unsigned long long

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

string s;
int num[4], cnt = 1, a, b, l[4];
bool f1, f2, f3, is_p;

int make_0(int l) {
    int i = 1;
    if (!l) return 1;
    while (l--) i *= 10;
    return i;
}

int make_9(int l) {
    int i = 0;
    while (l--) { i *= 10; i += 9; }
    return i;
}

signed main() {
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '.') {
            if (s[i + 1] == '(') { f2 = 1; cnt = 3; }
            else { f3 = 1; cnt = 2; }
        }
        if (s[i] == '(') { is_p = 1; cnt = 3; }
        if (s[i] >= '0' && s[i] <= '9') {
            num[cnt] *= 10, num[cnt] += (s[i] - '0');
            l[cnt]++;
        }
    }

    f1 = (!is_p);
    if (f1) {
        a = num[1] * make_0(l[2]) + num[2];
        b = make_0(l[2]);
    } else if (f2) {
        a = num[3];
        b = make_9(l[3]);
        a = a + num[1] * b;
    } else if (f3) {
        a = num[2] * make_0(l[3]) + num[3] - num[2];
        b = make_9(l[3]) * make_0(l[2]);
        a = a + num[1] * b;
    }

    cout << a / gcd(a, b) << '/' << b / gcd(a, b);
    return 0;
}

输入数据满足 $1\le |s|\le 10^3$。试完成以下判断题和单选题。

28. 删去第 14 行对输出不造成影响。

{{ select(28) }}

• 正确
• 错误

29.（2 分）输入 2024.06(191620) 时，输出为 707713249/349650。

{{ select(29) }}

• 正确
• 错误

30. 输入 1 会导致程序出现运行错误。

{{ select(30) }}

• 正确
• 错误

31.（2 分）输入 2(1) 时，输出为（ ）。

{{ select(31) }}

• 0/0
• 21/1
• 2/1
• 运行时错误

32. 分别记第 40～42 行、第 43～46 行、第 47～50 行为代码【块 1】、【块 2】和【块 3】。当输入为 .2(2) 时，将调用（ ）。

{{ select(32) }}

• 【块 1】
• 【块 2】
• 【块 3】
• 【块 2】、【块 3】

33.（4 分）当输入为 .21629(629) 时，$a$ 与 $b$ 的值分别为（ ）。

{{ select(33) }}

• 146，675
• 146000，675000
• 21608，99900
• 21608000，99900000

三、完善程序（共 2 题、10 个空，每空 3 分，共计 30 分）

第 1 题：相等最大权值定量变换（第 34～38 题）

给定数列 $\{b_n\}$。数列 $\{a_n\}$ 初始各项均为 1。

每次可以选择正整数 $i,x$（$1\le i\le n$），将 $a_i$ 变为 $a_i+\left\lfloor\dfrac{a_i}{x}\right\rfloor$，其中 $\lfloor z\rfloor$ 表示对 $z$ 向下取整。

最多可以进行 $k$ 次操作，操作后若 $a_i=b_i$ 可以得到得分 $c_i$，求出最大得分。

已知：$1\le n\le 10^3$，$1\le k\le 10^6$，$1\le b_i\le 10^3$，$1\le c_i\le 10^6$。

提示：考虑预处理出对于所有 $x$，$1\to x$ 所需的最小操作数 $f_x$。不难发现，本题目的本质是一个背包问题，直接 DP 即可。

试补全以下程序。

#include <bits/stdc++.h>

#define N 1000010
#define M 1000
#define INF 1000010
#define ll long long

using namespace std;

inline ll rd();
ll n, k, cnt, sum, b[N], c[N], f[N], dp[N];
ll mx = 1;

void init() {
    for (int i = 1; i <= M; i++)
        f[i] = INF;
    f[1] = 0;
    for (int i = 1; i <= M; i++)
        for (int j = 1; j <= i; j++)
            /* Blank 1 */;
    mx = max(mx, f[i + i / j]);
}

int main() {
    init();
    n = rd(), k = rd();
    for (int i = 1; i <= n; i++) {
        b[i] = rd();
        /* Blank 2 */;
    }
    for (int i = 1; i <= n; i++)
        c[i] = rd(), sum += c[i];
    if (/* Blank 3 */) {
        printf("%lld\n", sum);
        return 0;
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++)
        /* Blank 4 */
            /* Blank 5 */
    printf("%lld\n", dp[k]);
    return 0;
}

inline ll rd() {
    char c;
    bool flag = 0;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-') flag = 1;
    ll res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + c - '0';
    return flag ? -res : res;
}

34. 第 /* Blank 1 */ 空应该填（ ）。

{{ select(34) }}

• f[i + i / j] = min(f[i + i / j], f[i])
• f[i + i / j] = min(f[i + i / j], f[i] + 1)
• f[i + (i + 1) / j] = min(f[i + (i + 1) / j], f[i])
• f[i + (i + 1) / j] = min(f[i + (i + 1) / j], f[i] + 1)

35. 第 /* Blank 2 */ 空应该填（ ）。

{{ select(35) }}

• sum += b[i]
• sum += f[b[i]]
• cnt += b[i]
• cnt += f[b[i]]

36. 第 /* Blank 3 */ 空应该填（ ）。

{{ select(36) }}

• k >= cnt
• k >= cnt * n
• k >= sum
• k >= sum * n

37. 第 /* Blank 4 */ 空应该填（ ）。

{{ select(37) }}

• for (int j = k; j >= f[b[i]]; j--)
• for (int j = k; j; j--)
• for (int j = f[b[i]]; j <= k; j++)
• for (int j = 1; j <= k; j++)

38. 第 /* Blank 5 */ 空应该填（ ）。

{{ select(38) }}

• dp[j] = min(dp[j - f[b[i]]], dp[j] + c[i]);
• dp[j] = min(dp[j - f[b[i]]] + c[i], dp[j]);
• dp[j] = max(dp[j - f[b[i]]], dp[j] + c[i]);
• dp[j] = max(dp[j - f[b[i]]] + c[i], dp[j]);

第 2 题：最大边权最短路（第 39～43 题）

给定一张 $n$ 个结点、$m$ 条边的无向有权图，求 $s$ 到 $t$ 的所有路径中，最大边权的最小值。

保证 $1\le n,m\le 10^5$，且保证边权均为不超过 $10^6$ 的正整数。

下面的程序使用二分答案加 DFS 解决该问题，时间复杂度为 $O((n+m)\log w)$，尝试补全代码。

#include <bits/stdc++.h>
using namespace std;

int n, m, s, t;
bool vis[100005];
struct edge {
    int to, dis;
};
vector<edge> g[100005];

bool check(int maxdis, int cur) {
    if (cur == t) return true;
    if (/* Blank 1 */) return false;
    vis[cur] = true;
    for (int i = 0; i < g[cur].size(); i++)
        if (g[cur][i].dis <= maxdis && /* Blank 2 */)
            return true;
    /* Blank 3 */
}

int main() {
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    int l = 0, r = /* Blank 4 */;
    while (l < r) {
        int mid = (l + r) / 2;
        memset(vis, 0, sizeof vis);
        if (check(mid, s))
            r = mid;
        else
            l = /* Blank 5 */;
    }
    cout << l;
    return 0;
}

39. 第 /* Blank 1 */ 空应该填（ ）。

{{ select(39) }}

• vis[cur]
• cur > maxdis
• maxdis <= 0
• g[cur].size() == 0

40. 第 /* Blank 2 */ 空应该填（ ）。

{{ select(40) }}

• check(g[cur][i].dis, g[cur][i].to)
• check(min(maxdis, g[cur][i].dis), i)
• check(maxdis + g[cur][i].dis, g[cur][i].to)
• check(maxdis, g[cur][i].to)

41. 第 /* Blank 3 */ 空应该填（ ）。

{{ select(41) }}

• vis[cur] = false; return false;
• vis[cur] = false; return true;
• return false;
• return vis[cur];

42. 第 /* Blank 4 */ 空应该填（ ）。

{{ select(42) }}

• n
• m
• 10000000000
• 1000000

43. 第 /* Blank 5 */ 空应该填（ ）。

{{ select(43) }}

• mid
• mid + (l + r) % 2
• mid - 1
• l + 1