本卷程序代码均使用原卷高分辨率截图；题号已按 Hydro 作答顺序扁平化为 1～42。

一、选择题（每题 2 分，共 30 分）

1. 下列算法中，用于求最小生成树的是（　）。

{{ select(1) }}

• KMP 算法
• Prim 算法
• Floyd 算法
• Tarjan 算法

2. 对数组 39, 7, 36, 27, 80 使用 $Base=8$ 的基数排序使得从小到大有序，第一轮结束后的结果是（　）。

{{ select(2) }}

• 80, 36, 7, 27, 39
• 7, 27, 36, 39, 80
• 80, 27, 36, 39, 7
• 80, 27, 36, 7, 39

3. 中缀表达式 5<<4+3*2<<1 等价于后缀表达式（　）。

{{ select(3) }}

• 5 4 3 2 * + << 1 <<
• 5 4 << 3 2 * 1 << +
• 5 4 3 2 * + 1 << <<
• 前三个答案都不对

4. yummy 编译 C++ 源代码 game.cpp 获得了可执行文件 A。假设他希望可执行文件从文件 B 输入，文件 C 输出，并且运行时在 game.cpp 的 main 函数内填入一个参数 "D"，那么他在 Linux 终端里输入的命令应该是（　）。

{{ select(4) }}

• ./A D < B > C
• ./A D < C > B
• ./A D B C
• ./A < D > B C

5. 考虑一个长为 2026 的字符串 $s$，使用 $s[l,\ldots,r]$ 表示 $s$ 中第 $l$ 到 $r$ 个字符构成的子串，$r_i$ 为最大的 $r\ge 0$ 使得 $s[i-r,\ldots,i+r]$ 是回文串。如果 $r_{100}=70$，$r_{80}=60$，那么 $r_{120}$ 至少是（　）。

{{ select(5) }}

• 20
• 50
• 60
• 前三个选项都不对

6. 在一片足够空旷的平地上，一个微型机器人以“前进 1 厘米，左转 $60^\circ$，前进 1 厘米，左转 $60^\circ$，前进 1 厘米，右转 $60^\circ$，前进 1 厘米，右转 $30^\circ$”为周期运动。那么，它第一次回到起点时，运动的总路程是（　）厘米。

{{ select(6) }}

• 48
• 12
• 4
• 前三个答案都不对

7. 现有两个 int 型变量 $a,b$，满足 $0<b<a\le 10^9$。令 $p$ 为 $a,b$ 按位异或的结果，$q$ 为 $a,b$ 的最大公因数，那么（　）。

{{ select(7) }}

• $p\ge q$，等号可能取到。
• $p\le q$，等号可能取到。
• $p>q$。
• $p<q$。

8. 对于集合 $A,B$，定义 $A\oplus B=(A\cup B)\setminus(A\cap B)$。给出函数

$$f(S)= \begin{cases} 0, & S=\varnothing,\\ \displaystyle\min_{x=1}^{n}\bigl(f(S\oplus\{x\})+w(S,x)\bigr), & S\ne\varnothing, \end{cases}$$

其中 $w(S,x)\ge 0$。在不假设 $w$ 的任何其他性质时，想要求解 $f(\{1,\ldots,n\})$，下列算法中最合适的是（　）。

{{ select(8) }}

• 动态规划
• 贪心法
• Dijkstra 算法
• Floyd 算法

9. 一张 $n$（$n\ge 4$）个结点、$m$ 条边的简单无向连通二分图具有欧拉回路。那么下列说法错误的是（　）。

{{ select(9) }}

• 若结点 1 在左部，则有且仅有一种方法把所有结点划分为左部和右部。
• 左部和右部均至少有 2 个结点。
• $m$ 一定是偶数。
• $n$ 一定是偶数。

阅读以下材料，完成第 10 至 12 题。

维护颜色段是一个经典的问题。对于一个序列 $a_1,\ldots,a_n$，如果 $a_l,a_{l+1},\ldots,a_r$ 全部相等，并且 $a_{l-1}\ne a_l$、$a_r\ne a_{r+1}$（特别地，认为 $a_0=a_{n+1}=+\infty$），则称 $[l,r]$ 为一个颜色段。例如，1, 1, 5, 3, 3, 1 共有四个颜色段 $[1,2],[3,3],[4,5],[6,6]$。

现在我们需要一种数据结构：给出序列 $a_1,\ldots,a_n$，需要支持区间赋值、区间数颜色段个数，且总操作次数为 $O(n)$ 次。Alice 和 Bob 选用了不同的方法。

10. Alice 选择使用线段树维护序列

$$b_i= \begin{cases} 0, & a_i=a_{i+1},\\ 1, & a_i\ne a_{i+1}, \end{cases}$$

支持单点修改、区间求和。下列说法正确的是（　）。

{{ select(10) }}

• 她写的线段树必须有懒标记（lazy-tag）。
• 这棵线段树如果使用树状数组代替，那么时间复杂度增加。
• 如果要求子串 $a[100,\ldots,200]$ 的颜色段个数，那么需要计算序列 $b$ 在 $[100,199]$ 上的和。
• 使用这棵线段树，还能对于每个下标 $i$ 查询它所在颜色块的右端点，但是时间复杂度为 $\Theta(\log^2 n)$。

11. Bob 选择维护一个 set<int> s 记录所有颜色段的左端点，然后每次查询时遍历区间内的颜色块实现计数，称为“珂朵莉树”。想要查询包含下标 $i$ 所在的颜色块右端点 $r$，表达式正确的是（　）。

{{ select(11) }}

• r=*--s.lower_bound(i)
• r=*s.lower_bound(i)-1
• r=*--s.upper_bound(i)
• r=*s.upper_bound(i)-1

12. Alice 和 Bob 在讨论各自做法的时间复杂度。下列说法正确的是（　）。

{{ select(12) }}

• 使用 Alice 的做法，每次操作最坏 $O(\log n)$。
• 使用 Alice 的做法，总时间复杂度为 $O(n\log n)$。
• 使用 Bob 的做法，每次操作最好 $O(n)$。
• 使用 Bob 的做法，如果输入的区间、操作类型、赋值均随机，总时间复杂度为 $O(n^2)$。

13. 已知 $p$ 为一个 $1\sim 6$ 的全排列，对任意 $1\le i\le 6$ 均有 $p(p(p(p(i))))=i$。这样的排列 $p$ 有（　）种。

{{ select(13) }}

• 256
• 301
• 376
• 456

14. 同余方程 $x^3\equiv 909\pmod {1001}$ 有（　）组解满足 $0\le x<1001$。

{{ select(14) }}

• 1
• 3
• 9
• 27

15. 一棵二叉树的前序遍历为 C, 1, D, 8, 4, 5, 3, A, 2, 7, 6, B，中序遍历为 4, 8, D, 3, 5, 2, A, 7, 1, C, 6, B，其中 $A,B,C,D$ 中 $9\sim 12$ 各出现了一次。

定义 $\operatorname{LCA}(x,y)$ 为 $x,y$ 的最近公共祖先。已知 $\operatorname{LCA}(4,9)=12$，$\operatorname{LCA}(2,10)=C$，$\operatorname{LCA}(1,11)=11$，那么 $A,B,C,D$ 中，最大的数字是（　）。

{{ select(15) }}

• $A$
• $B$
• $C$
• $D$

二、阅读程序（无特殊说明时判断题 1.5 分，选择题 3 分，共 40 分）

第 1 组程序（12 分）

输入数据保证：$1\le n,m\le 10^6$，$s$ 是长度为 $n$ 的小写英文字母字符串。

16. 程序输出的字符串长度取决于 $n$ 的大小。

{{ select(16) }}

• 正确
• 错误

17. 若将代码第 15 行 mx=0 更换为 mx=-1，程序的输出结果不变。

{{ select(17) }}

• 正确
• 错误

18.（2 分）若将代码第 17 行的 > 更换为 >=，程序的输出结果不变。

{{ select(18) }}

• 正确
• 错误

19. 程序输出的第一个字符取决于（　）。

{{ select(19) }}

• $s$ 的第一个字符。
• $s$ 的最后一个字符。
• $s$ 的最后一个字符在 $s$ 中所有出现位置的下一个位置出现次数最多的字符，出现次数相同则选字典序较小者。
• $s$ 的最后一个字符在 $s$ 中所有出现位置的下一个位置出现次数最多的字符，出现次数相同则选字典序较大者。

20.（4 分）若输入为 10 7 daedacbace，则输出为（　）。

{{ select(20) }}

• dacbacb
• daedaed
• acbacba
• aebaeba

第 2 组程序（14 分）

输入数据保证：$1\le n,m\le 10^6$，$1\le u,v\le n$，$u\ne v$，$x\in\{0,1\}$。

21. 若将代码 34～37 行的整个 do-while 语句替换为 init();，代码的时间复杂度不变。

{{ select(21) }}

• 正确
• 错误

22. 对于任何合法的输入数据，该程序输出结果不会超过 $m$，且可能为 $m$。

{{ select(22) }}

• 正确
• 错误

23.（2 分）代码 34～37 行的 do-while 语句，可能导致变量 top 变为负数进而导致程序运行时错误。

{{ select(23) }}

• 正确
• 错误

24.（2 分）假设将 Find 操作的均摊时间复杂度视为 $O(1)$，并且 $n,m$ 同阶，则该算法的时间复杂度可以视为（　）。

{{ select(24) }}

• $O(n)$
• $O(n\log n)$
• $O(n^2)$
• $O(n\sqrt n)$

25. 若输入为 4 5 1 2 1 2 3 1 3 4 1 4 1 0 4 1 1，则输出为（　）。

{{ select(25) }}

• 1
• 2
• 3
• 4

26.（4 分）当 $n=3,m=4$ 时，有（　）种合法的输入可以使该程序输出 1。

{{ select(26) }}

• 4992
• 4896
• 5184
• 5088

第 3 组程序（14 分）

输入数据保证：$1\le n,m\le 100$，$s,t$ 分别是长度为 $n,m$ 的小写英文字母字符串。

27. 当字符串 $s$ 为 aabaaab 时，bd 序列为 {0,1,0,1,2,2,3}。

{{ select(27) }}

• 正确
• 错误

28. 代码第 61 行的判断是没有必要的，在执行第 61 行前变量 ans 不可能为负数。

{{ select(28) }}

• 正确
• 错误

29.（2 分）若 $s$ 不是 $t$ 的子序列，输出结果一定为 0。

{{ select(29) }}

• 正确
• 错误

30.（2 分）若删除代码第 25 行 while 循环中 x>0 的判断，程序可能出现的错误是（　）。

{{ select(30) }}

• 输出答案错误（WA）
• 超出时间限制（TLE）
• 超出空间限制（MLE）
• 运行时错误（RE）

31. 若输入为 3 8 csp aaacspaa，则输出为（　）。

{{ select(31) }}

• 102
• 144
• 120
• 160

32.（4 分）当 $m=5$ 时，程序输出值最大可能是（　）。

{{ select(32) }}

• 249
• 251
• 253
• 255

三、完善程序（单选题，每小题 3 分，共 30 分）

组合问题（15 分）

构造一个长度为 $m$ 的序列 $a_1,a_2,\ldots,a_m$，每个元素都是不超过 $n$ 的正整数，其中整数 $i$ 恰好有 $x_i$ 个，$m=\sum_{1\le i\le n}x_i$。

求出满足要求的不同序列数量。以下代码求解了上述问题，请补全程序。

33. /* Blank 1 */ 处应该填（　）。

{{ select(33) }}

• 0
• mod
• mod-1
• mod-2

34. /* Blank 2 */ 处应该填（　）。

{{ select(34) }}

• ifac[i]=ifac[i+1]*(i)%mod
• ifac[i]=ifac[i+1]*(i+1)%mod
• ifac[i]=ifac[i+1]*inv(i)%mod
• ifac[i]=ifac[i+1]*inv(i+1)%mod

35. /* Blank 3 */ 处应该填（　）。

{{ select(35) }}

• fac[x]*ifac[y]%mod
• fac[x]*ifac[x-y]%mod
• fac[x]*ifac[y]%mod*ifac[x-y]%mod
• fac[x-y]*ifac[y]%mod

36. /* Blank 4 */ 处应该填（　）。

{{ select(36) }}

• 0
• 1
• fac[n]
• ifac[n]

37. /* Blank 5 */ 处应该填（　）。

{{ select(37) }}

• (ans*=C(sum,x[i]))%=mod
• (ans+=C(sum,x[i]))%=mod
• (ans*=C(sum+x[i],x[i]))%=mod
• (ans+=C(sum+x[i],x[i]))%=mod

边权差最短路（15 分）

给定一个含 $n$ 个点、$m$ 条边的带权无向图，边权为整数，起点为 1，终点为 $n$，保证至少存在一条从 1 到 $n$ 的路径。

对于一条从起点到终点的路径，定义该路径的花费为：将经过的所有边权按顺序写下来后，该序列相邻元素差的绝对值之和。求从 1 到 $n$ 的最小总费用。

以下代码求解了上述问题，请补全程序。

38. /* Blank 1 */ 处应该填（　）。

{{ select(38) }}

• pos<_.pos
• pos>_.pos
• dis<_.dis
• dis>_.dis

39. /* Blank 2 */ 处应该填（　）。

{{ select(39) }}

• e[i][j].dis-e[i][j+1].dis
• e[i][j+1].dis-e[i][j].dis
• e[i][j].dis
• e[i][j].dis+e[i][j+1].dis

40. /* Blank 3 */ 处应该填（　）。

{{ select(40) }}

• 1
• m
• m+1
• m+2

41. /* Blank 4 */ 处应该填（　）。

{{ select(41) }}

• vis[u]==1
• dis[u]==inf
• u>n
• u>m

42. /* Blank 5 */ 处应该填（　）。

{{ select(42) }}

• dis[n]
• dis[m]
• dis[m+1]
• dis[m+2]