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

---

一、 单项选择题

1. 答案：C 解析：这是一个经典的插空法问题。先将 5 个红球排成一排，它们之间以及两端共产生 6 个空位。为了保证 5 个蓝球互不相邻，必须将这 5 个蓝球放入这 6 个空位中，且每个空位最多放 1 个。因此，排列方法数为组合数 $C_6^5 = 6$ 种。

2. 答案：A 解析：KMP 算法的 next 数组（此处定义为 $P[0..i]$ 的最长公共前后缀长度，且通常为了对齐会多一个起始位或题目特指长度为 $m+1$ 的数组）。 对于 $P = \text{abacaba}$：

• 长度 0 (空串): 0
• 长度 1 ("a"): 0
• 长度 2 ("ab"): 0
• 长度 3 ("aba"): 1 (前缀 "a" = 后缀 "a")
• 长度 4 ("abac"): 0
• 长度 5 ("abaca"): 1 (前缀 "a" = 后缀 "a")
• 长度 6 ("abacab"): 2 (前缀 "ab" = 后缀 "ab")
• 长度 7 ("abacaba"): 3 (前缀 "aba" = 后缀 "aba") 得到的序列为 $\{0, 0, 0, 1, 0, 1, 2, 3\}$，与选项 A 完全匹配。

3. 答案：B 解析：线段树查询区间 $[3, 11]$ 的过程如下：

• 访问根节点 $[0, 15]$ (1个)
• 拆分到左子树 $[0, 7]$ 和右子树 $[8, 15]$ (2个)
• $[0, 7]$ 拆分为 $[0, 3]$ 和 $[4, 7]$。其中 $[4, 7]$ 完全包含在 $[3, 11]$ 中，直接返回 (1个完全包含节点)。$[0, 3]$ 继续拆分。
• $[0, 3]$ 拆分为 $[0, 1]$ (无交集，不访问) 和 $[2, 3]$。$[2, 3]$ 继续拆分。
• $[2, 3]$ 拆分为 $[2, 2]$ (无交集) 和 $[3, 3]$。$[3, 3]$ 完全包含 (1个完全包含节点)。
• $[8, 15]$ 拆分为 $[8, 11]$ 和 $[12, 15]$ (无交集)。其中 $[8, 11]$ 完全包含 (1个完全包含节点)。 总计访问的节点为：$[0, 15], [0, 7], [8, 15], [0, 3], [4, 7], [2, 3], [3, 3], [8, 11]$，共 8 个节点。

4. 答案：D 解析：构建 Trie 树并统计节点数（包括根节点）：

• 根节点 (1)
• c (2) $\rightarrow$ a (3) $\rightarrow$ t (4), r (5) $\rightarrow$ t (6), s (7) $\rightarrow$ e (8)
• d (9) $\rightarrow$ o (10) $\rightarrow$ g (11) 共计 11 个节点。

5. 答案：D 解析：有向无环图 (DAG) 的拓扑排序数量取决于图的结构。如果是链状图，只有 1 种；如果是没有任何边的图，有 $n!$ 种。因此“只有 1 种”、“最多 $n$ 种”、“等于 $n-m$ 种”均不成立，选“以上都不对”。

6. 答案：D 解析：哈希表大小为 13，线性探查 $H(\text{key}) = \text{key} \bmod 13$。

• 18 $\bmod$ 13 = 5 $\rightarrow$ 放入位置 5
• 26 $\bmod$ 13 = 0 $\rightarrow$ 放入位置 0
• 35 $\bmod$ 13 = 9 $\rightarrow$ 放入位置 9
• 9 $\bmod$ 13 = 9 $\rightarrow$ 位置 9 冲突，探查 10 $\rightarrow$ 放入位置 10
• 68 $\bmod$ 13 = 3 $\rightarrow$ 放入位置 3
• 74 $\bmod$ 13 = 9 $\rightarrow$ 位置 9 冲突，探查 10 (冲突)，探查 11 $\rightarrow$ 放入位置 11。

7. 答案：A 解析：要使完全图的最小生成树总权重最小，应尽可能选择权重小的边。边权为 $|u-v|$，最小的边权为 1。我们可以选择连接相邻编号的顶点：(1,2), (2,3), (3,4), (4,5), (5,6), (6,7), (7,8)。这 7 条边的权重均为 1，且恰好连接了所有 8 个顶点形成一棵树，总权重为 $7 \times 1 = 7$。

8. 答案：A 解析：二叉搜索树的后序遍历最后一个元素是根节点，即 6。

• 左子树元素均小于 6：2, 5, 4。其后序遍历为 2, 5, 4，根为 4，左子为 2，右子为 5。
• 右子树元素均大于 6：8, 12, 10。其后序遍历为 8, 12, 10，根为 10，左子为 8，右子为 12。 树的结构确定后，前序遍历（根-左-右）为：6, 4, 2, 5, 10, 8, 12。

9. 答案：D 解析：0-1 背包问题，容量 20。 物品：(7, 15), (5, 12), (4, 9), (3, 7), (6, 13)。 尝试组合：选择重量为 7, 4, 3, 6 的物品，总重量 $7+4+3+6 = 20 \le 20$。 总价值为 $15 + 9 + 7 + 13 = 44$。这是能达到的最大价值。

10. 答案：D 解析：已知结点 1 是整棵树的根节点。根据 LCA 的定义，任何结点与根节点 1 的最近公共祖先必然是根节点 1 本身。因此 $LCA(12, 1) = 4$ 是绝对不可能出现的（除非 4 就是 1，但题意显然指代不同结点）。

11. 答案：C 解析：使用主定理 (Master Theorem)。$T(n) = 2T(n/2) + O(n^2)$。 这里 $a=2, b=2, f(n) = n^2$。 $n^{\log_b a} = n^{\log_2 2} = n^1 = n$。 因为 $f(n) = n^2 = \Omega(n^{1+\epsilon})$ (其中 $\epsilon=1$)，且满足正则条件 $2(n/2)^2 = n^2/2 \le c n^2$ (取 $c=1/2 < 1$)，所以时间复杂度由 $f(n)$ 决定，即 $O(n^2)$。

12. 答案：A 解析：模拟最小堆的插入与删除：

• 插入 20, 12, 15, 8, 10, 5 后，堆的结构为：[5, 10, 8, 20, 12, 15]。
• 第一次 delete-min：移除 5，将末尾的 15 移到堆顶并下沉，堆变为：[8, 10, 15, 20, 12]。
• 第二次 delete-min：移除 8，将末尾的 12 移到堆顶并下沉，堆变为：[10, 12, 15, 20]。 此时堆顶元素为 10。

13. 答案：A 解析：使用容斥原理计算 1 到 1000 中能被 2, 3, 5 整除的数的个数：

• $|A_2| = 500, |A_3| = 333, |A_5| = 200$
• $|A_2 \cap A_3| = \lfloor 1000/6 \rfloor = 166$
• $|A_2 \cap A_5| = \lfloor 1000/10 \rfloor = 100$
• $|A_3 \cap A_5| = \lfloor 1000/15 \rfloor = 66$
• $|A_2 \cap A_3 \cap A_5| = \lfloor 1000/30 \rfloor = 33$ 能被整除的总数 = $500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$。 不能被整除的数 = $1000 - 734 = 266$。

14. 答案：C 解析：朴素递归计算斐波那契数列时，会反复计算相同的子问题（如计算 $F(5)$ 需要计算 $F(3)$，计算 $F(4)$ 也需要计算 $F(3)$），存在大量的重叠子问题。动态规划通过存储已计算的结果（记忆化或自底向上）避免了这种重复计算，从而将时间复杂度从指数级降为线性。

15. 答案：B 解析：这是一个经典的带截止时间调度问题（最小化延迟惩罚）。最优的贪心策略是：优先处理截止时间最早的任务。如果在安排过程中发现当前任务无法在截止时间前完成，则从已安排的任务中剔除处理时间最长的任务（因为惩罚等于处理时长，剔除它能最大程度释放时间并减少惩罚）。因此，优先执行截止时间最早的任务 $A_3$ 是正确策略的起点。

---

二、 阅读程序

(1) 限制相邻递增的排列生成

16. 答案：A (正确) 解析：$n=3$ 时，全排列共 6 种。其中包含相邻递增对（如 12, 23）的有：123, 231, 312。合法的排列只有：132, 213, 321，共 3 种。程序输出 3，正确。

17. 答案：A (正确) 解析：dfs 初始调用为 dfs(1)，每次递归调用 dfs(k+1)，直到 k == n + 1 时触发基线条件返回。因此 $k$ 的取值范围确实是 $1 \le k \le n+1$。

18. 答案：B (错误) 解析：flag[i] = false 是回溯算法恢复状态的关键步骤。如果删除，数字一旦被使用就会被永久标记，导致无法生成其他排列，最终答案会错误地变为 1。

19. 答案：A 解析：求 $n=4$ 时无相邻递增对（即不包含 12, 23, 34 作为子串）的排列数。使用容斥原理：

• 总排列：$4! = 24$
• 至少包含 1 个相邻递增对：$3 \times 3! = 18$
• 至少包含 2 个相邻递增对（即 123 或 234 或 12和34）：$2! + 2! + 2! = 6$ （注：123 和 34 不能同时存在，所以是 123, 234, {12, 34} 三种情况，每种看作 2 个元素排列，共 $3 \times 2 = 6$）
• 至少包含 3 个相邻递增对（即 1234）：$1! = 1$ 非法排列数 = $18 - 6 + 1 = 13$。合法排列数 = $24 - 13 = 11$。

20. 答案：D 解析：数组 p 仅在 $k > 1$ 时被读取 p[k-1]。而 p[k-1] 的值是在上一层递归中通过 p[k-1] = i 显式赋值的。因此，p 数组在进入 dfs 前的初始值根本不会被读取，对程序运行没有任何影响。

21. 答案：C 解析：删除 flag 检查后，数字可以重复使用。我们需要生成长度为 3 的序列，每个位置可选 1, 2, 3，但不能出现 $p[k] = p[k-1] + 1$。

• 第 1 位：3 种选择。
• 第 2 位：若第 1 位是 1，第 2 位可选 1, 3 (2种)；若是 2，可选 1, 2 (2种)；若是 3，可选 1, 2, 3 (3种)。共 7 种前缀。
• 第 3 位：对这 7 种前缀分别计算合法的第 3 位选择数，分别为 2, 3, 2, 2, 2, 2, 3。总和为 $2+3+2+2+2+2+3 = 16$。

(2) 猜数字游戏（双鸡蛋问题）

22. 答案：A (正确) 解析：

• 输入 "6 5 1"：guess1 线性扫描，依次检查 1, 2, 3, 4, 5。在 5 时返回 true，共检查 5 次。
• 输入 "6 5 2"：guess2 中 $w=3$ ($3 \times 4 / 2 \ge 6$)。第一次检查 $h=3$ (false)；第二次检查 $h=3+2=5$ (true, 碎了)；然后在区间 $[4, 4]$ 线性检查 $h=4$ (false)。最后断言 5 正确。共检查 3, 5, 4，共 3 次。

23. 答案：B (错误) 解析：存在反例。例如 $n=2, k=1$。

• $t=1$ 时，检查 1 即中，猜测数为 1。
• $t=2$ 时，$w=2$。先检查 2 (true, 碎了)，再检查 1 (true, 碎了)，猜测数为 2。此时 $t=2$ 的猜测数大于 $t=1$。

24. 答案：A (正确) 解析：guess1 遍历 $1 \dots n$，必然命中。guess2 是经典的 2 个鸡蛋测临界楼层的最优策略，其步长递减的设计保证了在最多碎 2 次的情况下，能够精确覆盖 $1 \dots n$ 的所有可能，必然能猜到正确结果。

25. 答案：B 解析：在 guess1 中，一旦 check(i) 返回 true，程序会立即执行 assert_ans(i) 并 return 退出函数。因此 cnt_broken 最多只会被增加 1 次。

26. 答案：C 解析：guess2 中，外层循环执行 $w$ 次，内层循环最多执行 $w-1$ 次。总猜测次数最多为 $2w-1$。因为 $w \approx \sqrt{2n}$，所以猜测次数的量级为 $O(\sqrt{n})$。

27. 答案：A 解析：$n=100$。

• $t=1$ 时，最坏情况（$k=100$）需要检查 100 次。
• $t=2$ 时，$w(w+1)/2 \ge 100 \Rightarrow w=14$ ($14 \times 15 / 2 = 105$)。最坏情况发生在 $k=99$ 或 $k=100$ 时。以 $k=99$ 为例：外层检查 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 (共 11 次，第 11 次为 true)。然后内层线性检查 96, 97, 98 (共 3 次)。总次数 $11 + 3 = 14$ 次。

(3) 折半搜索求解方程

28. 答案：B (错误) 解析：代码后半部分使用了双指针算法来寻找 ans1[las] + ans2[i] == 0 的组合。双指针算法的正确性严格依赖于两个数组都是有序的。如果删除对 ans2 的排序，las 的单调递增性质将被破坏，会导致大量漏解。

29. 答案：A (正确) 解析：mpow 函数通过二进制拆分指数（k >>= 1, x = x * x），是标准的快速幂算法，用于在 $O(\log k)$ 时间内计算 $x^k$。

30. 答案：A (正确) 解析：第 39-50 行遍历已排序的 ans1，如果当前元素与前一个相同，则将其频次 cntans1 加 1；否则将其作为新元素存入，并初始化频次为 1。这是标准的“去重并统计频次”操作。

31. 答案：B 解析：输入 $n=3, m=15$，系数和指数为 $(1, 2), (-1, 2), (1, 2)$。 方程为：$1 \cdot x_1^2 - 1 \cdot x_2^2 + 1 \cdot x_3^2 = 0 \Rightarrow x_1^2 + x_3^2 = x_2^2$。 即求 $x_i \in [1, 15]$ 范围内的勾股数 $(x_1, x_3, x_2)$ 的排列数。 满足条件的勾股数组合有：(3,4,5), (4,3,5), (6,8,10), (8,6,10), (5,12,13), (12,5,13), (9,12,15), (12,9,15)，共 8 组。

32. 答案：D 解析：折半搜索将 $n$ 个变量分为两半，每半枚举 $m^{n/2}$ 种状态。

• 生成状态时，每次调用 mpow 耗时 $O(\log P)$，生成总耗时 $O(m^{n/2} \log P)$。
• 排序 ans1 和 ans2 耗时 $O(m^{n/2} \log m^{n/2})$。
• 双指针匹配耗时 $O(m^{n/2})$。 综合起来，总时间复杂度为 $O(m^{n/2}(\log m^{n/2} + \log P))$。

33. 答案：D 解析：DFS 中的循环为 for (int i = 1; i <= m; ++i)，说明变量 $x_i$ 的取值范围是 $[1, m]$。程序最终统计的是 ans1[las] + ans2[i] == 0 的组合数，即求解方程 $\sum_{i=1}^{n} k_i \cdot x_i^{p_i} = 0$ 的整数解的数量。

---

三、 完善程序

(1) 特殊最短路（分层图 Dijkstra）

34. 答案：A 解析：初始状态下，位于起点 $s$，且尚未使用过免费边，因此 used_freebie 状态应为 0。

35. 答案：B 解析：这是 Dijkstra 算法的标准优化。如果当前从优先队列取出的距离 dist 大于已经记录在该状态下的最短距离 d[u][used]，说明这是一个过期的状态，应直接 continue 跳过。

36. 答案：B 解析：此处处理的是不使用免费边的正常转移。到达节点 $v$ 的距离增加 $w$，且 used 状态保持不变。因此更新的是 d[v][used]。

37. 答案：C 解析：当 used == 0 时，可以尝试使用免费边。此时经过该边的费用为 0，到达 $v$ 的距离等于当前距离 d[u][0]，且状态变为 used = 1。因此，应该用 d[u][0] 去尝试更新 d[v][1]。

38. 答案：C 解析：到达终点 $t$ 时，可能使用了免费边，也可能没有使用。为了求最小总费用，应取这两种状态下的最小值，即 min(d[t][0], d[t][1])。

(2) 组合测试方案生成与解码

39. 答案：B 解析：根据信息论，$w$ 轮测试可能产生的不同结果总数（即长度为 $w$ 且 1 的个数 $\le k$ 的二进制串数量）必须不少于生产线数量 $n$，才能保证唯一确定缺陷生产线。因此循环条件为 count_patterns(w, k) < n。

40. 答案：B 解析：代码中通过 fill(bits.begin(), bits.begin() + ones, 1) 初始化数组，这使得数组的前 ones 个元素为 1，其余为 0（例如 1, 1, 0, 0）。这是字典序最大的排列。为了遍历所有包含 ones 个 1 的组合，必须使用 prev_permutation 使其按字典序递减，直到变成 0, 0, 1, 1。

41. 答案：D 解析：plan[i] 存储的是第 $i$ 轮测试中包含的生产线编号。根据 code 矩阵的定义，code[j][i] == 1 表示第 $j$ 条生产线在第 $i$ 轮被取样测试。

42. 答案：A 解析：题目说明 signature 的最低位对应第 1 批次（即 $i=0$）。因此，提取第 $i$ 批次检测结果（0 或 1）的标准位运算操作是 (signature >> i) & 1。

43. 答案：B 解析：解码阶段，需要找到 code 矩阵中与测试结果 sig_bits 完全匹配的那一行。该行的索引 $j$ 即为存在缺陷的生产线编号。因此条件为 code[j] == sig_bits。