一、单项选择题解析

1. B ｜ chmod 用于修改文件或目录权限。grep 用于文本查找，pwd 用于显示当前目录，echo 用于输出文本。

2. C ｜ 先计算：$13 = (1101)_2$，$10 = (1010)_2$，所以：$13 \& 10 = (1000)_2 = 8$。再计算：$12 = (1100)_2$，$5 = (0101)_2$，所以：$12 \oplus 5 = (1001)_2 = 9$。最后：$8 | 9 = 9$。

3. A ｜ 外层中 $i$ 依次为：$1, 2, 4, 8, \ldots$ 固定 $i$ 时，内层循环大约执行 $\frac{n}{i}$ 次。总次数为：$n + \frac{n}{2} + \frac{n}{4} + \cdots$ 这是等比级数，复杂度为 $O(n)$。

4. C ｜ 快速排序如果每次选择第一个元素作为基准，且输入已经升序排列，那么每次划分都会极不均衡。递归规模变为：$n, n-1, n-2, \ldots$ 总复杂度为 $O(n^2)$。

5. B ｜ 4个元素按固定顺序进栈，所有可能出栈序列数量为第4个卡特兰数：$C_4 = \frac{1}{5}\binom{8}{4} = 14$

6. B ｜ 深度为5的满二叉树结点数为：$1 + 2 + 4 + 8 + 16 = 31$

7. C ｜ 有向无环图中，若给顶点排一个拓扑序，只能从前面的点向后面的点连边。最多边数为：$\binom{7}{2} = 21$

8. D ｜ 要求 $7x \equiv 1 \pmod{26}$。尝试 $x = 15$：$7 \times 15 = 105$。$105 \mod 26 = 1$。所以逆元为15。

9. C ｜ ABCBDAB和BDCABA的最长公共子序列长度为4。例如BCBA、BDAB都是长度为4的公共子序列。

10. D ｜ 限制为：1在3前；2在3前；2在4前。若第一个为1，之后必须先放2，再放3, 4，后两者任意，共2种。若第一个为2，剩下1, 3, 4中只要求1在3前，共3种。总数为：$2 + 3 = 5$。

11. B ｜ 这是最小生成树的环性质。如果一条边是某个环上权值唯一最大的边，那么它一定不在任何最小生成树中。

12. A ｜ 两枚骰子共有36种等可能结果。点数和为7的情况有：$(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1)$。共6种，所以概率为：$\frac{6}{36} = \frac{1}{6}$。

13. C ｜ 可选方案中：物品1和物品4：重量 $2 + 5 = 7$，价值 $3 + 8 = 11$。物品2和物品3：重量 $3 + 4 = 7$，价值 $4 + 5 = 9$。其他合法组合价值不超过11。所以最大价值为11。

14. C ｜ 设非叶结点数为 $x$。每个非叶结点有3个儿子，所以边数为 $3x$。树有40个结点，因此边数为39。于是：$3x = 39$，得到 $x = 13$。叶结点数为：$40 - 13 = 27$。

15. B ｜ 递归式：$T(n) = 3T(n/2) + O(n)$。根据主定理，$a = 3, b = 2$，有：$n^{\log_b a} = n^{\log_2 3}$。由于 $O(n)$ 小于 $n^{\log_2 3}$，所以：$T(n) = O(n^{\log_2 3})$。

二、程序阅读题解析

第1题解析

这段程序计算的是KMP中常用的前缀函数。$p_i$ 表示字符串前缀 $s[0..i]$ 的最长相等真前后缀长度。

16. A（正确） ｜ 数组p初始为0，循环从 $i = 1$ 开始，不会修改 $p[0]$。所以 $p_0$ 始终为0。

17. A（正确） ｜ 输入为aaaa。前缀函数数组为：$0, 1, 2, 3$。所以最后一项为3，最大值为3，总和为6。输出：3 3 6

18. A（正确） ｜ 若所有字符两两不同，则任何长度大于0的相等真前后缀都不存在。所有 $p_i$ 都为0，输出：0 0 0

19. A ｜ 输入为ababa。前缀函数数组为：$0, 0, 1, 2, 3$。最后一项为3，最大值为3，总和为6。输出：3 3 6

20. D ｜ 输入为abcabca。前缀函数数组为：$0, 0, 0, 1, 2, 3, 4$。所以 $p_6 = 4$。

21. A ｜ 前缀函数算法中，指针 $j$ 总体只会有限次回退和前进，总复杂度为线性。因此时间复杂度为 $\Theta(n)$。

第2题解析

这段程序使用状态压缩动态规划统计从1号点出发，经过每个点恰好一次的路径数量。状态 $dp[s][u]$ 表示已经访问的点集为 $s$，当前停在 $u$ 的路径数量。

22. A（正确） ｜ 初始状态为：dp[1][0] = 1。下标0对应编号1的顶点，所以所有统计的路径都从1号点开始。

23. A（正确） ｜ 4个点的完全图中，从1号点出发，剩余3个点可以任意排列。共有：$3! = 6$ 条哈密顿路径。

24. B（错误） ｜ 程序最后只统计访问了所有顶点的路径：dp[(1<<n)-1][i]。所以它统计的是从1号点出发的哈密顿路径数量，不是所有简单路径数量。

25. A ｜ 图是一条链：$1 - 2 - 3 - 4$。从1出发并访问所有点恰好一次，只能走：$1 \to 2 \to 3 \to 4$。所以输出为1。

26. B ｜ 图是一个4点环：$1 - 2 - 3 - 4 - 1$。从1出发的哈密顿路径有两条：$1 \to 2 \to 3 \to 4$ 和 $1 \to 4 \to 3 \to 2$。所以输出为2。

27. C ｜ 状态数为 $2^n \cdot n$。每个状态会枚举下一个点 $v$，最多 $n$ 种。所以时间复杂度为：$\Theta(n^2 \cdot 2^n)$。

第3题解析

这段程序使用Floyd算法求无向图所有点对最短路。最后统计所有可达的有序点对数量，并输出最大有限最短路和可达有序点对数量。

28. A（正确） ｜ 读入边时使用：min(d[u][v], w)。所以如果有重边，会保留边权最小的一条。

29. B（错误） ｜ 如果图不连通，程序不会输出-1。它只会忽略不可达点对，统计所有有限距离中的最大值和数量。

30. A（正确） ｜ 初始化时：d[i][i] = 0。因此每个 $(i, i)$ 都满足 $d[i][i] < INF$，会被cnt统计。

31. B ｜ 图中1, 2, 3连通，4孤立。1到3的最短路为：$1 \to 2 \to 3$，长度 $3 + 4 = 7$，优于直接边10。在点1, 2, 3中共有 $3 \times 3 = 9$ 个有序可达点对，再加上 $(4, 4)$，所以cnt=10。最大有限最短路为7。输出：7 10

32. C ｜ Floyd算法三重循环枚举中转点、起点、终点。时间复杂度为：$\Theta(n^3)$。

33. B ｜ 输入边时程序同时设置：d[u][v] = d[v][u]。所以它求的是无向图的所有点对最短路。

三、完善程序题解析

第1题：区间最大值查询

ST表中，st[j][i] 表示从位置 $i$ 开始，长度为 $2^j$ 的区间最大值。转移时，将长度为 $2^j$ 的区间拆成两个长度为 $2^{j-1}$ 的区间。询问 $[l, r]$ 时，取 $k = \lfloor\log_2(r - l + 1)\rfloor$，用两个长度为 $2^k$ 的区间覆盖即可。

34. A ｜ 预处理对数数组：lg[i] = lg[i >> 1] + 1

35. B ｜ 第 $j$ 层对应长度 $2^j$，循环条件应为：(1 << j) <= n

36. C ｜ 右半段起点为：$i + 2^{j-1}$。所以应填：st[j - 1][i + (1 << (j - 1))]

37. A ｜ 询问区间长度为：$r - l + 1$。所以：int k = lg[r - l + 1]

38. D ｜ 两个覆盖区间为：$[l, l+2^k-1]$ 和 $[r-2^k+1, r]$。所以答案为：max(st[k][l], st[k][r - (1 << k) + 1])

第2题：01边权最短路

边权只有0和1时，可以使用0-1BFS。如果经过一条权值为0的边，新的状态应放到队首；如果经过一条权值为1的边，新的状态放到队尾。这样可以保证队列中的距离大致按从小到大处理。

39. A ｜ 题目给的是有向图，边为 $u \to v$，边权为 $w$。所以应加入：g[u].push_back({v, w})

40. C ｜ 从 $u$ 经过边权 $w$ 到达 $v$，新距离为：d[u] + w

41. A ｜ 如果边权为0，新状态优先级更高，应加入队首：q.push_front(v)

42. B ｜ 如果边权为1，新状态加入队尾：q.push_back(v)

43. D ｜ 如果 $t$ 不可达，$d[t]$ 仍为INF，应输出 $-1$。否则输出 $d[t]$：(d[t] == INF ? -1 : d[t])