以下是 2023 年 CSP-S 第一轮试题的详细解答与解析：

---

一、 单项选择题

1. 答案：B
解析：在 Linux 系统中，mkdir (make directory) 是用于创建新目录的标准命令。

2. 答案：A
解析：组成四位数，首位不能为 0，有 4 种选择（1, 2, 3, 4）。剩下的 3 个位置从剩余的 4 个数字中选 3 个进行排列，有 $A_4^3 = 4 \times 3 \times 2 = 24$ 种。总方案数为 $4 \times 24 = 96$。

3. 答案：A
解析：对于稀疏图，$m = \Theta(n)$，代入各选项：

• A: $O(n \sqrt{\log n} \log \log n)$
• B: $O(n^2 + n) = O(n^2)$
• C: $O(n^2 / \log n + n \log n)$
• D: $O(n + n \log n) = O(n \log n)$ 比较 A 和 D，当 $n$ 足够大时，$\sqrt{\log n} \log \log n < \log n$ 恒成立，因此 A 的渐近时间复杂度最小。

4. 答案：C
解析：这是一个经典的搜索/图论问题。要求相邻圆环编号之和为完全平方数。对于 4 根柱子，通过构造或搜索可知，最多可以放置 11 个圆环（例如一种合法放置为：柱1: 8,1；柱2: 7,2；柱3: 6,3；柱4: 5,4,11，其中 4+5=9, 5+11=16，均满足条件）。

5. 答案：B
解析：哈夫曼树（Huffman Tree）是一种带权路径长度最短的二叉树，主要用于数据压缩（如哈夫曼编码），与图的深度优先搜索（DFS）无关。

6. 答案：A
解析：完全三叉树是二分图，二分图一定可以用 2 种颜色进行合法染色。平面图可能需要 4 种颜色（四色定理），边双连通图和欧拉图都可能包含奇环（如三角形），需要 3 种颜色。

7. 答案：C
解析：序列 $X$: A B C A A A A B A，序列 $Y$: A B A B C B A B A。 它们的最长公共子序列 (LCS) 可以是 A B C A B A 或 A B A A B A 等，长度均为 6。

8. 答案：B
解析：设第一次掷出 $x$，第二次掷出 $y$。收益为：若 $y=x$ 则为 0，若 $y \neq x$ 则为 $2x$。 期望收益 $E = \sum_{x=1}^{6} P(x) \times [P(y=x) \times 0 + P(y \neq x) \times 2x]$ $E = \sum_{x=1}^{6} \frac{1}{6} \times \left( \frac{5}{6} \times 2x \right) = \frac{5}{18} \sum_{x=1}^{6} x = \frac{5}{18} \times 21 = \frac{105}{18} = \frac{35}{6}$ 元。

9. 答案：A
解析：a=5 (0101), b=3 (0011), c=4 (0100)。

• a & b = 0101 & 0011 = 0001 (1)
• c ^ b = 0100 ^ 0011 = 0111 (7)
• a | c = 0101 | 0100 = 0101 (5) 表达式为 1 || 7 && 5。根据优先级，&& 高于 ||，且非零整数在逻辑运算中视为 true。 7 && 5 结果为 true (1)。 1 || 1 结果为 true。res 是 bool 类型，值为 true。

10. 答案：C
解析：快速排序在输入已排序且总是选择第一个元素作为基准时，每次划分都会产生一个大小为 0 和一个大小为 $n-1$ 的子数组，导致递归树退化为链状，时间复杂度退化为 $O(n^2)$。

11. 答案：A
解析：g++ 编译命令中，-o 选项用于指定输出文件名，其后紧跟可执行文件名，最后是源文件。即 g++ -o main main.cpp。

12. 答案：C
解析：树的重心性质：偶数个节点的树可能有两个重心（如一条包含偶数个节点的链，中间两个节点均为重心）；而奇数个节点的树一定只有一个重心。选项中只有 7 是奇数。

13. 答案：C
解析：图中无拓扑序说明存在环。要使其能进行拓扑排序，必须打破所有环。删除的边必须属于图中所有环的交集。根据该经典真题图的结构，共有 3 条边满足此条件（即删除其中任意一条都能破坏所有环）。

14. 答案：B
解析：$f(n)$ 为十六进制各位数字之和。不动点为 9，意味着经过若干次 $f$ 操作后最终结果为 9。 在 $[100_{16}, 1A0_{16}]$ (即十进制 $[256, 416]$) 范围内，数的十六进制形式为 $1xy_{16}$。 第一次操作后 $n_1 = 1 + x + y$。因为 $x \le 9, y \le 15$，所以 $n_1 \le 1+9+15 = 25$。 在 $[1, 25]$ 中，最终能变成 9 的数只有 9 和 $18_{16}$ (十进制 24，因为 $1+8=9$)。

• 若 $n_1 = 9$，则 $1 + x + y = 9 \Rightarrow x + y = 8$。$(x,y)$ 有 $(0,8), (1,7), \dots, (8,0)$ 共 9 组。
• 若 $n_1 = 24$，则 $1 + x + y = 24 \Rightarrow x + y = 23$。满足条件的 $(x,y)$ 有 $(8,15)$ 即 $18F_{16}$，和 $(9,14)$ 即 $19E_{16}$，共 2 组。（注意 $19F_{16}$ 超出 $1A0_{16}$ 范围，但 $19E_{16} = 414 \le 416$，合法）。 总计 $9 + 2 = 11$ 个。

15. 答案：A
解析：代码中 quick_power(x, n / 2) 被调用了两次，且没有记忆化。其时间复杂度递推式为 $T(n) = 2T(n/2) + O(1)$，根据主定理，时间复杂度为 $O(n)$，失去了快速幂 $O(\log n)$ 的优势。

---

二、 阅读程序

(1) 位运算变换

16. 答案：A (正确)
解析：该变换在 GF(2) 上是可逆的线性变换，不存在非零的零化点，因此输入非零时输出一定不为零。

17. 答案：B (错误)
解析：unsigned short 在参与运算时会提升为 int，但在赋值回 unsigned short 时会发生截断（保留低 16 位）。如果参数改为 unsigned int，则不会发生截断，输出结果会改变。

18. 答案：A (正确)
解析：输入 65535 (16 个 1)。x << 6 后低 6 位为 0，x ^ (x << 6) 结果为高 6 位为 0，低 10 位为 1，即 63。63 >> 8 为 0，63 ^ 0 仍为 63。

19. 答案：B (错误)
解析：输入 1。1 << 6 = 64。1 ^ 64 = 65。65 >> 8 = 0。65 ^ 0 = 65。输出为 65，不是 64。

20. 答案：B
解析：输入 512 ($2^9$)。512 << 6 = 32768。512 ^ 32768 = 33280。33280 >> 8 = 130。33280 ^ 130 = 33410。

21. 答案：D
解析：输入 64 ($2^6$)。64 << 6 = 4096。64 ^ 4096 = 4160。

(2) 约数和函数

22. 答案：B (错误)
解析：第 15 行 reverse 确保 d 中的质数幂是从大到小遍历的。如果删去，从小到大遍历会导致合数被其最小质因子的低次幂先标记，从而无法正确记录最高次幂 g[j]，导致后续约数和计算错误。

23. 答案：B (错误)
解析：solve1 计算 $\sum_{i=1}^n \sigma(i)$（约数和），solve2 通过交换求和顺序计算 $\sum_{i=1}^n i \cdot \lfloor n/i \rfloor$，两者在数学上完全等价。输入 10 时，两行输出均为 87，第一行不大于第二行。

24. 答案：A (正确)
解析：同上，对于任意 $n$，两行输出始终相等。

25. 答案：D
解析：solve1 是线性筛的变种，内层循环每个合数只被其最小质因子访问一次，时间复杂度为 $O(n \log \log n)$。

26. 答案：B
解析：solve2 只有一个从 1 到 $n$ 的循环，每次操作 $O(1)$，时间复杂度为 $O(n)$。

27. 答案：B
解析：输入 5。solve2(5) = $1\times5 + 2\times2 + 3\times1 + 4\times1 + 5\times1 = 5 + 4 + 3 + 4 + 5 = 21$。

(3) 二分答案求差值对数

28. 答案：A (正确)
解析：原代码 h = m，若改为 h = m - 1（假设题意如此），由于 f0 是单调的，若 $m$ 满足条件，则 $m-1$ 可能满足也可能不满足。若不满足，下一轮 g 会变为 $m$，循环结束，输出不变；若满足，则继续缩小范围，最终仍能正确找到最小满足条件的 $m$。

29. 答案：A (正确)
解析：在 $g, h \ge 0$ 的前提下，g + (h - g) / 2 与 (h + g) >> 1 在整数运算中完全等价，输出不变。

30. 答案：A (正确)
解析：输入排序后为 -4, -3, 1, 2, 5。求差值 $\le m$ 的对数 $\ge 7$ 的最小 $m$。 差值对按大小排序：1(2对), 3(1对), 4(2对), 5(2对)。 当 $m=4$ 时，累计 5 对 $< 7$；当 $m=5$ 时，累计 7 对 $\ge 7$。故最小 $m$ 为 5，输出 5。

31. 答案：C
解析：排序耗时 $O(n \log n)$。二分查找的范围是 $A = a.back() - a[0] + 1$，二分次数为 $O(\log A)$。每次 f0 检查耗时 $O(n)$。总时间复杂度为 $O(n \log n + n \log A) = O(n \log(nA))$。

32. 答案：B
解析：原代码 a[i] - a[j] > m 计算的是差值 $\le m$ 的对数。改为 >= 后，计算的是差值 $< m$ 的对数。 对于同一个 $m$，新代码算出的对数 $\le$ 原代码算出的对数。为了让对数达到 $k$，新代码需要更大的 $m$。 因此，现输出 $\ge$ 原输出。题目问“原输出与现输出的大小关系”，即“原输出 $\le$ 现输出”，对应选项“一定小于等于且不一定小于”。

33. 答案：B
解析：输入排序后为 -12, -5, 2, 3, 8。求差值 $\le m$ 的对数 $\ge 8$ 的最小 $m$。 差值对按大小排序：1(1), 5(1), 6(1), 7(2), 8(1), 13(1), 14(1)。 当 $m=13$ 时，累计 7 对 $< 8$；当 $m=14$ 时，累计 8 对 $\ge 8$。故输出 14。

---

三、 完善程序

(1) 第 k 小路径

34. 答案：B
解析：在候选节点中按字典序遍历，如果当前节点 $u$ 的路径总数 $f[u] \ge k$，说明第 $k$ 小路径就在以 $u$ 为起点的路径中，直接返回 $u$。

35. 答案：A
解析：拓扑排序中，当节点的入度减为 0 时可以入队。代码中先判断后执行 --deg[v]，因此判断条件应为 deg[v] == 1，减完后即为 0。

36. 答案：A
解析：从 $u$ 出发的路径数等于 1 (自身) 加上所有后继节点 $v$ 的路径数之和。为防止溢出，需与 LIM 取最小值：std::min(f[u] + f[v], LIM)。

37. 答案：D
解析：f[u] 包含了以 $u$ 为终点的长度为 1 的路径。如果 $k=1$，说明当前节点 $u$ 就是我们要找的终点，无需继续向下扩展。因此循环条件为 $k > 1$。

38. 答案：C
解析：在决定走向下一个节点前，需要排除掉“路径就在当前节点 $u$ 结束”的这一种情况，因此将 $k$ 减 1，即 --k。

(2) 最大值之和

39. 答案：D
解析：pre 数组初始化为 a[mid ... r-1]。循环目的是求从 mid 开始向右的区间最大值，因此 pre[i] 应更新为 pre[i] (即 a[mid+i]) 和 pre[i-1] 的较大值。

40. 答案：B
解析：max 记录了左半部分 a[i ... mid-1] 的最大值。while 循环向右扩展右端点 j，只要 a[j] < max，说明区间 [i, j] 的最大值仍然是 max。当遇到 a[j] >= max 时停止，此时 j 是右边第一个 $\ge max$ 的位置。

41. 答案：A
解析：对于固定的左端点 $i$，右端点在 [mid, j-1] 范围内的所有区间，其最大值都是 max。这样的区间共有 j - mid 个，总贡献为 (long long)(j - mid) * max。

42. 答案：C
解析：对于左端点 $i$，右端点在 [j, r-1] 范围内的区间，其最大值由右半部分决定。sum 数组是 pre 的前缀和，因此这部分区间的最大值之和正好等于 sum[r - mid] - sum[j - mid]。

43. 答案：A
解析：分治算法的初始调用应覆盖整个数组，下标范围为 0 到 n（左闭右开），即 solve(0, n)。