参考答案与详细解析

一、 单项选择题

1. B。插空法。6 个蓝球产生 7 个空隙（包括两端），从中选 4 个位置放入红球，方案数为 $C(7, 4) = 35$。
2. A。$P = \text{ababaca}$。
   • $i=0$: a $\rightarrow 0$
   • $i=1$: ab $\rightarrow 0$
   • $i=2$: aba $\rightarrow 1$ (a)
   • $i=3$: abab $\rightarrow 2$ (ab)
   • $i=4$: ababa $\rightarrow 3$ (aba)
   • $i=5$: ababac $\rightarrow 0$ (前缀 a 与后缀 c 不匹配，且无更短匹配)
   • $i=6$: ababaca $\rightarrow 1$ (a) 结果为 $\{0, 0, 1, 2, 3, 0, 1\}$。
3. C。线段树查询区间 $[2, 13]$ 访问的节点为：[0,15], [0,7], [8,15], [0,3], [4,7](完全包含), [2,3](完全包含), [8,11](完全包含), [12,15], [12,13](完全包含)。共 9 个节点。
4. C。Trie 树节点：root(1), a(1), p(1), p(1, app结束), l(1), e(1, apple结束), y(1, apply结束), e(1, ape结束), b(1), a(1), t(1, bat结束), g(1, bag结束)。共 12 个节点。
5. B。DAG 存在唯一拓扑排序的充要条件是图中存在一条包含所有顶点的有向路径（即哈密顿路径），此时拓扑序唯一且相邻顶点间必有边。
6. B。二次探查 $H_i = (H(key) + i^2) \bmod 11$。
   • 23: $23 \bmod 11 = 1$
   • 34: $34 \bmod 11 = 1$ (冲突), $i=1 \rightarrow (1+1)\bmod 11 = 2$
   • 45: $45 \bmod 11 = 1$ (冲突), $i=1 \rightarrow 2$(满), $i=2 \rightarrow (1+4)\bmod 11 = 5$
   • 12: $12 \bmod 11 = 1$ (冲突), $i=1 \rightarrow 2$(满), $i=2 \rightarrow 5$(满), $i=3 \rightarrow (1+9)\bmod 11 = 10$
   • 56: $56 \bmod 11 = 1$ (冲突), $i=1 \rightarrow 2$(满), $i=2 \rightarrow 5$(满), $i=3 \rightarrow 10$(满), $i=4 \rightarrow (1+16)\bmod 11 = 6$。
7. B。边权 $w(u, v) = u \times v$。为最小化总权重，每个顶点 $v > 1$ 应直接连接到顶点 1，边权为 $v \times 1 = v$。总权重 = $2+3+4+5+6 = 20$。
8. A。后序最后是 A，故根为 A。中序中 A 分割左右子树：左 D B E，右 F C。左子树后序 D E B，根为 B，中序 D B E 分割得左 D 右 E。右子树后序 F C，根为 C，中序 F C 分割得左 F。前序遍历为：根-左-右 $\rightarrow$ A B D E C F。
9. C。容量 15。物品：(3,8), (4,10), (5,12), (6,15), (7,18)。最优组合为选重量 3, 5, 7 的物品，总重量 $3+5+7=15$，总价值 $8+12+18=38$。
10. D。1 是整棵树的根节点，任何节点与根节点 1 的 LCA 必然是 1。因此 $LCA(12, 1) = 4$ 是不可能出现的。
11. C。主定理：$a=3, b=3, f(n) = n \log n$。$n^{\log_b a} = n^1 = n$。$f(n) = \Theta(n^{\log_b a} \log^1 n)$，属于主定理第二种情况的扩展，时间复杂度为 $O(n \log^2 n)$。
12. C。最大堆插入后为：30 (根), 左子 25, 右子 15; 25 的子节点为 20, 10; 15 的子节点为 5。

• 删除 30：5 移至根，下沉与 25 交换，再与 20 交换。堆变为：25, 20, 15, 5, 10。
• 删除 25：10 移至根，下沉与 20 交换。堆变为：20, 10, 15, 5。堆顶为 20。

13. B。容斥原理。$N=1000$。

• $|A|=333, |B|=200, |C|=142$
• $|A \cap B|=66, |A \cap C|=47, |B \cap C|=28$
• $|A \cap B \cap C|=9$
• 能被整除的数 = $333+200+142 - 66-47-28 + 9 = 543$。
• 不能被整除的数 = $1000 - 543 = 457$。

14. B。分治法在合并时需要 $O(n)$ 时间计算跨越中点的最大子段和，存在大量重复计算；而 Kadane 算法通过 $O(1)$ 的状态转移（dp[i] = max(a[i], dp[i-1] + a[i])）避免了重复计算，将复杂度降至 $O(n)$。
15. B。这是经典的带截止时间调度问题（最小化延迟惩罚等价于最大化按时完成的任务权重）。最优贪心策略为：按截止时间排序依次尝试加入，若总时间超过当前任务截止时间，则剔除已选任务中处理时间最长的任务（Moore-Hodgson 算法思想）。

二、 阅读程序

（1）

16. A (正确)。$n=3$ 时，全排列 6 种。排除含有相邻递增对（如 12, 23）的排列：123, 231, 312。剩余合法排列为：132, 213, 321，共 3 种。
17. A (正确)。初始调用 dfs(1)，递归调用 dfs(k+1)，直到 k == n + 1 时触发基线条件返回，故 $k$ 会取到 $n+1$。
18. B (错误)。flag[i]=false 是回溯算法恢复状态的标准操作。若删除，数字被标记后将无法在后续分支中使用，导致答案错误（通常变为 1 或 0）。
19. A。$n=4$ 时，总排列 24 种。利用容斥原理计算包含 "12", "23", "34" 的排列数：$3 \times 3! - 3 \times 2! + 1 \times 1! = 18 - 6 + 1 = 13$。合法排列数 = $24 - 13 = 11$。
20. D。p 数组仅在 $k > 1$ 时读取 p[k-1]，而 p[k-1] 的值是在上一层 dfs 中被显式赋值的（p[k] = i）。因此 p 的初始值不会被读取，对程序无影响。
21. C。删除 flag 检查后，相当于每个位置可选 $1 \dots n$，但不能出现 $i = p[k-1] + 1$。使用 DP 计算：$k=1$ 时有 3 种；$k=2$ 时以 1, 2, 3 结尾的序列数分别为 3, 2, 2；$k=3$ 时分别为 7, 4, 5。总和为 $7+4+5=16$。

（2）

22. A (正确)。$t=1$ 时线性扫描，$k=5$ 需检查 1,2,3,4,5，共 5 次。$t=2$ 时，$w=3$ ($3 \times 4 / 2 \ge 6$)。先查 3 (False)，再查 $3+2=5$ (True, 碎了)，然后在区间 $[4, 4]$ 线性查 4 (False)，最后断言 5 正确。共调用 check 3 次。
23. B (错误)。反例：$n=6, k=1$。$t=1$ 时查 1 即中，共 1 次。$t=2$ 时 $w=3$，先查 3 (True, 碎了)，再查 1 (True, 碎了)，共 2 次。此时 $t=2$ 的猜测数大于 $t=1$。
24. A (正确)。$t=1$ 遍历必定命中；$t=2$ 是经典的“两枚鸡蛋”最优策略，步长递减保证了在最多碎 2 次的情况下能精确覆盖 $1 \dots n$ 的所有可能。
25. B。guess1 中一旦 check(i) 返回 true，就会立即执行 assert_ans 并 return，因此 cnt_broken 最多增加到 1。
26. C。guess2 的步长 $w$ 满足 $w(w+1)/2 \ge n$，即 $w \approx \sqrt{2n}$。最坏情况下猜测次数为 $w$ 次，量级为 $O(\sqrt{n})$。
27. A。$t=1$ 最坏需 100 次。$t=2$ 时，$w(w+1)/2 \ge 100 \Rightarrow w=14$ ($14 \times 15 / 2 = 105$)。最坏情况（如在 14 碎了，需线性检查 1~13）共 $1 + 13 = 14$ 次。

（3）

28. B (错误)。第 55 行的双指针逻辑依赖于 ans1 升序且 ans2 降序遍历（即 ans2 必须是有序的）。若删除 sort(ans2)，las 的单调递增假设被破坏，会导致漏解。
29. A (正确)。mpow 是标准的快速幂算法，通过二进制拆分指数在 $O(\log k)$ 时间内计算 $x^k$。
30. A (正确)。代码遍历排序后的 ans1，若当前元素与前一个相同则频次 +1，否则存入新位置并初始化频次为 1，这是标准的去重并统计频次操作。
31. B。输入表示求 $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]$。即求 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. C。折半搜索将 $n$ 个变量分为两半，每半枚举 $m^{n/2}$ 种状态。排序 ans1 耗时 $O(m^{n/2} \log m^{n/2})$，双指针匹配耗时 $O(m^{n/2})$。总时间复杂度为 $O(m^{n/2} \log m^{n/2})$。
33. D。DFS 中循环为 for (int i = 1; i <= m; ++i)，且最终统计 ans1[las] + ans2[i] == 0 的组合数，即求 $\sum_{i=1}^{n} k_i \cdot x_i^{p_i} = 0$ 且 $x_i \in [1, m]$ 的整数解的数量。

三、 完善程序

（1）特殊最短路

34. A。初始在起点 $S$，尚未使用免费边，故 used_freebie 状态为 0。
35. B。Dijkstra 标准优化：若当前取出的距离 dist 大于已记录的最小距离 d[u][used]，说明该状态已过期，跳过。
36. B。正常走边（不使用免费边），更新到达 $v$ 且 used 状态不变的最小距离，即 d[v][used]。
37. C。使用免费边时，前提是 used == 0。此时到达 $v$ 的距离不变（费用为 0），状态变为 used = 1。因此比较的是 d[u][0] 与 d[v][1]。
38. C。到达终点 $T$ 时，可能使用了免费边，也可能未使用，取两者最小值 min(d[t][0], d[t][1])。

（2）组合测试

39. B。根据信息论，可能的测试结果总数（长度为 $w$ 且 1 的个数 $\le k$ 的二进制串数量）必须不少于生产线数量 $n$，即 count_patterns(w, k) < n 时 $w$ 不够，需增加。
40. A。bits 初始化为前 ones 个为 1，其余为 0。使用 next_permutation 可字典序生成所有包含 ones 个 1 的排列组合。
41. D。plan[i] 存储第 $i$ 轮测试包含的生产线编号。根据 code 矩阵，若 code[j][i] == 1，表示第 $j$ 条生产线在第 $i$ 轮被测试。
42. A。signature 的最低位对应第 1 批次（$i=0$），因此提取第 $i$ 位的操作为 (signature >> i) & 1。
43. B。解码时，只需找到 code 矩阵中与测试结果 sig_bits 完全匹配的那一行，其行号 $j$ 即为存在缺陷的生产线编号。