📚 覆盖：第 28–34 讲 · 重点：题 4、6、9、13、16 是本单元的核心。
第一部分：分治（第 28 讲）
题 1（4 分）
(a) 分治适用的三个条件是什么？哪一个是它与动态规划的分界线？ (b) 最大子数组的分治解是 Θ(n log n)，Kadane 是 Θ(n)。这说明什么？ (c) 观察分治算法汇总表，为什么"减少子问题个数"比"加快合并"收益更大？
题 2（5 分）
(a) 朴素分治大整数乘法是 4T(n/2)+Θ(n)，为什么没有改进？
(b) 写出 Karatsuba 的代数恒等式，说明如何把 4 次乘法降到 3 次。
(c) Strassen 把 8 次降到 7 次，复杂度从 Θ(n³) 变成什么？
(d) 为什么 Strassen 在小矩阵上反而更慢？列出三个原因。
题 3（5 分）
(a) 证明最近点对算法中"带内每点只需检查后 7 个点"。 (b) 为什么必须预排序并在递归中维护 y 有序？不这么做复杂度是多少？ (c) 用矩阵快速幂在 Θ(log n) 内求第 n 个斐波那契数，写出转移矩阵。
第一部分之二：回溯（第 29 讲）
题 3.5（7 分）⭐
(a) 回溯的三要素是什么？Go 中保存结果为什么必须 slices.Clone(path)，不拷贝会出现什么症状？
(b) 子集枚举用 start、排列枚举用 used，为什么不能反过来？
(c) 含重复元素的排列去重条件是 !used[i-1]，为什么不是 used[i-1]？两种写错分别导致什么结果？
(d) N 皇后的两条对角线如何编号成一维下标？这把什么复杂度降成了什么？
(e) 剪枝的四种手段是什么？哪一种实践收益往往最大，为什么？
(f) 分支限界的"界"为什么必须乐观？这与 A* 的哪个条件对应？0-1 背包的界为什么能用分数背包算？
(g) 说明"DP 是回溯 + 记忆化"，并解释为什么"先写回溯再优化"比"直接猜贪心"更可靠。
第二部分：贪心（第 30 讲）
题 4（7 分）⭐
(a) 贪心需要哪两个性质？与 DP 的关系是什么？ (b) 活动选择的四种候选策略中，为什么"最早结束"是对的？给出另外三种的反例。 (c) 完整证明活动选择的贪心选择性质。 (d) “最少会议室"为什么不能用同样的贪心？正确解法是什么？
题 5（5 分）
(a) 证明 Huffman 引理：频率最小的两个字符可以放在最深的兄弟位置。 (b) Huffman 是最优前缀码，为什么现代压缩器还要用算术编码？ (c) Huffman 今天仍在哪些格式中使用？为什么？
题 6（6 分）⭐
(a) 分数背包贪心正确而 0-1 背包错误，本质原因是什么？ (b) 给出 0-1 背包的贪心反例（三个物品即可）。 (c) 拟阵的两条公理是什么？说明"图的森林"满足它们。 (d) 用拟阵理论说明 Kruskal 的正确性。为什么活动选择不能用拟阵解释？ (e) 币制 {1,3,4} 求 6 元，贪心给什么？最优是什么？这说明什么？
第三部分：动态规划（第 31–32 讲）
题 7（5 分）
(a) DP 的两个前提是什么？缺少"重叠子问题"时该用什么？ (b) 写出"DP 复杂度 = ? × ?"，用它分析 LCS 和 0-1 背包。 (c) 记忆化与递推各有什么优劣？推荐什么工作流程？
题 8（5 分）
(a) 写出 LCS 的转移方程，解释"末尾相同时为什么可以直接 +1”。 (b) 用滚动数组优化到 Θ(n) 空间后失去了什么？如何补救？ (c) 编辑距离的三个 min 项分别对应哪种操作？
题 9（7 分）⭐
(a) 0-1 背包一维写法为什么必须倒序遍历容量？正序解的是什么问题？ (b) 什么是伪多项式时间？为什么 Θ(nW) 不算多项式？ (c) 这对 0-1 背包意味着什么？n=100、W=10⁹ 时该怎么办？ (d) 多重背包（每种 kᵢ 个）如何用二进制拆分优化？
题 10（5 分）
(a) LIS 的 DP 状态为什么定义成"以 a[i] 结尾"而不是"前 i 个"？
(b) 解释 O(n log n) 解法中 tails 数组的含义，为什么"用更小的值替换"是正确的。
(c) tails 数组本身是一个合法的 LIS 吗？
题 11（6 分）
(a) 区间 DP 的循环为什么必须按区间长度递增？ (b) 矩阵链乘中，加括号方式为什么能差 10 倍？给出计算。 (c) “戳气球"为什么要枚举最后戳破的而不是第一个？ (d) 最优 BST 与平衡树的优化目标有什么不同？
题 12（6 分）
(a) 写出树上最大独立集的两个状态和转移。 (b) 为什么树上是线性的、二分图上可用匹配、一般图上是 NP-完全的？ (c) 换根 DP 的两遍 DFS 各做什么？写出"根从 u 移到 v"的距离和转移。
题 13（6 分）⭐
(a) TSP 状压 DP 的状态、转移与复杂度是什么？
(b) 相比枚举排列改进了多少？填一张 n = 10/15/20/25 的对照表。
(c) mask & (mask-1) 和 mask & (-mask) 分别是什么？
(d) 为什么"枚举所有子集的子集"总复杂度是 Θ(3ⁿ)？
(e) 数位 DP 中为什么 tight 状态不能缓存？
第四部分：字符串（第 33 讲）
题 14（6 分）
(a) π[i] 的精确定义是什么？给 “aabaaab” 手工算出 π 数组。
(b) k = pi[k-1] 在做什么？为什么它是递归结构？
(c) 用势能法证明 KMP 是 Θ(n+m)，势能函数取什么？
(d) 这个论证与单调栈的"每个元素进出各一次"是什么关系？
题 15（5 分）
(a) 滚动哈希如何 O(1) 从一个窗口算出下一个？为什么必须做字符串验证？ (b) Rabin-Karp 什么时候优于 KMP？ (c) Trie 的查找复杂度为什么与集合大小无关？相比散列表多了什么能力？ (d) “文本固定模式多变"和"模式固定文本流式"分别该预处理哪一边？
第五部分：复杂性（第 34 讲）
题 16（8 分）⭐
(a) P 和 NP 的定义分别是什么？NP 中的 “N” 代表什么？ (b) 要证明 B 是 NP-难的，归约方向应是 A ≤_p B 还是 B ≤_p A？用一句话解释。 (c) Cook-Levin 定理说了什么？它为什么是整个理论的起点？ (d) 完成 3-SAT ≤_p 独立集 归约中 “(⟸)” 方向的证明。 (e) 最短路在 P 中而最长路是 NP-难，欧拉回路在 P 中而哈密顿回路是 NPC。这说明了什么？
题 17（7 分）
(a) 顶点覆盖的 2-近似算法是什么？给出完整的近似比证明。 (b) “NP-完全"是否意味着实践中解不了？为什么现代 SAT 求解器能处理百万变量？ (c) 列出遇到 NP-难问题的五条出路。 (d) 举三个"限制输入结构就让 NPC 问题变简单"的例子。 (e) 为什么"改变问题"常常是最有效的一条出路？
参考解答
题 1
(a) ① 子问题同构；② 子问题独立（不重叠）；③ 合并高效。第 ② 条是与 DP 的分界线——子问题重叠时必须记忆化，否则指数级重复计算。
(b) 说明分治不总是最优解。最大子数组的最优子结构其实是线性的（“以 i 结尾的最大子数组"只依赖 i−1），DP 更合适。遇到问题应先分析子问题之间的依赖关系，而不是先套框架。
(c) 因为主定理中 a 出现在指数上（n^{log_b a}），而 f(n) 只是加项。降低 a 直接改变了指数（8→7 使指数从 3 变成 2.807），而降低 f(n) 只可能改变低阶项或常数。
题 2
(a) T(n) = 4T(n/2) + Θ(n)：log₂4 = 2，主定理情形 1，解是 Θ(n²)——与竖式乘法同阶。
(b)
xy = x₁y₁·10ⁿ + (x₁y₀ + x₀y₁)·10^{n/2} + x₀y₀
(x₁+x₀)(y₁+y₀) = x₁y₁ + (x₁y₀+x₀y₁) + x₀y₀
⟹ x₁y₀+x₀y₁ = (x₁+x₀)(y₁+y₀) − x₁y₁ − x₀y₀
只需 x₁y₁、x₀y₀、(x₁+x₀)(y₁+y₀) 三次乘法（加减是 Θ(n)）：T(n)=3T(n/2)+Θ(n) = Θ(n^{1.585})。
(c) T(n) = 7T(n/2) + Θ(n²) = Θ(n^{log₂7}) = **Θ(n^{2.807})**。
(d) ① 常数大（7 次乘法之外还有 18 次矩阵加减）；② 需要额外内存存中间量 M₁..M₇；③ 数值稳定性差（大量减法导致误差累积）；④ 现代 BLAS 的 Θ(n³) 实现有极好的 SIMD 和缓存优化。
题 3
(a) 考察矩形 R = [midX − δ, midX + δ] × [p.y, p.y + δ]——即带内所有纵坐标在 p 之后 δ 之内的点。注意 R 以中线为对称轴（不是以 p 为角点），因此中线把它切成的左右两个 δ×δ 正方形，恰好一个整体位于左半平面、一个整体位于右半平面——这一点是整个论证的支点。
每个 δ×δ 正方形内至多 4 个点：否则把它四等分成 (δ/2)×(δ/2) 的小格，5 个点中必有两点落入同一小格（鸽笼原理），距离 ≤ (δ/2)·√2 ≈ 0.707δ < δ；而这两点同属左半或右半平面，与「δ 是各半平面内的最小距离」矛盾。
于是 R 内至多 8 个点（含 p 自己），p 只需与 y 序排在它之后的至多 7 个点比较。∎ 纵坐标之差超过 δ 的点距离已 > δ，无需比较——这正是「只看后面 7 个」而非「扫整条带」的依据。
(b) 若不维护，每层都要重新按 y 排序，T(n) = 2T(n/2) + Θ(n log n) = **Θ(n log²n)**。维护方法：像归并的逆过程一样，在 O(n) 内把已按 y 有序的数组拆成左右两份（各自仍按 y 有序）。
(c)
┌ F(n+1) ┐ ┌ 1 1 ┐^n ┌ F(1) ┐
│ F(n) │ = │ 1 0 │ × │ F(0) │
用快速幂算 2×2 矩阵的 n 次方，Θ(log n) 次矩阵乘法（每次 O(1)）。
题 3.5
(a) 状态（path）、选择列表、撤销。必须 Clone 是因为 path 是切片，撤销时会就地修改底层数组（第 5 讲的切片共享）。不拷贝的症状极具迷惑性：结果数量正确，但每一项内容都是最后一次的状态。
(b) 组合不关心顺序，start 强制下标递增，使 {1,2} 与 {2,1} 只产生一次；排列关心顺序，必须允许下标以任意次序出现，只能用 used 标记"该元素已在路径里”。反过来用：组合用 used 会产生重复（同一集合的各种排列），排列用 start 会漏掉绝大部分排列（只剩下标递增的那些）。
(c) 目标是只允许按下标顺序使用相同元素。!used[i-1] 表示前一个相同元素尚未被使用、当前却要用后一个——这正是"跳过前一个、直接用后一个"的分支，它与"用前一个、跳过后一个"产生完全相同的排列，应剪掉。
- 写成
used[i-1]：剪掉了合法分支（两个相同元素都用的情况），结果偏少 - 不写这个判断：结果重复
⚠️ 两种错误都不会报错，只会给出错误答案，所以必须理解而不是背诵。
(d) ↘ 方向上 row - col 恒定（加 n 避免负下标），↙ 方向上 row + col 恒定。这把每次 O(n) 的冲突检测降成 O(1) 的数组查表。
(e) ① 可行性剪枝；② 最优性剪枝；③ 搜索顺序启发；④ 对称性破除。③ 的收益往往最大（数独中"先填候选最少的格子"常带来 10–100 倍加速），因为尽早失败就能剪掉更大的子树——在第 3 层剪掉的分支，远多于在第 20 层剪掉的。
(f) 界必须乐观（不高估最优值），否则会把真正的最优解误判为"不可能更优"而剪掉。这与 A* 的可采纳性（h 从不高估）是同一个条件。分数背包是 0-1 背包的松弛——允许切分物品只会让最优值更大或相等，因此是合法的上界。
(g) 回溯遍历整棵解空间树；若不同分支会到达相同的子问题状态，就可以缓存该状态的结果，避免重复展开——这就是记忆化，也就是 DP。先写回溯更可靠：回溯的正确性来自穷举的完备性（几乎不会错），失败时的表现只是"慢”；而贪心失败时会静悄悄给出错误答案。先拿到一个正确但慢的版本再有依据地优化，比一上来猜贪心策略然后祈祷它对稳妥得多。
题 4
(a) ① 贪心选择性质（存在一个最优解包含贪心的选择）；② 最优子结构。贪心是 DP 的特例：当"最优选择可以在不看子问题解的情况下确定"时，DP 退化成贪心。
(b)
| 策略 | 反例 |
|---|---|
| 最早开始 | 一个超长活动 + 三个短活动 ⟹ 贪心得 1，最优得 3 |
| 最短持续 | A:[0,6] B:[5,8] C:[7,13]——B 最短但同时挡住 A 和 C ⟹ 贪心得 1，最优得 2 |
| 冲突最少 | 底排 4 个互不相交 [0,2] [4,6] [8,10] [12,14]；加 4 个 [1,5]、4 个 [9,13]、1 个 M=[5,9]。此时 M 的冲突数 2 严格最少，但选 M 会同时挡掉 [4,6] 与 [8,10] ⟹ 贪心得 3，最优得 4 |
最早结束正确，因为它为后面留下的时间最多。
(c) 设贪心第一个选结束最早的 a₁，OPT 的第一个活动是 b。由 a₁ 结束最早 f(a₁) ≤ f(b)。令 OPT′ = OPT − {b} + {a₁}：a₁ 比 b 结束更早，不会与 OPT 中 b 之后的活动冲突，故 OPT′ 可行且 |OPT′| = |OPT|。存在一个最优解包含 a₁。∎ 剩下的是同类子问题，归纳即得。
(d) 因为它不是"选最多互不冲突的"问题，而是**“求任意时刻的最大重叠数”。正确解法：按开始时间排序，用最小堆**维护各会议室的结束时间，能复用就复用，堆的最终大小即答案。
题 5
(a) 设 T 是最优树，a、b 是 T 中深度最大的一对兄弟，x、y 是频率最小的两个字符。不妨 freq(x) ≤ freq(y)、freq(a) ≤ freq(b)，由 x、y 频率最小有 freq(x) ≤ freq(a)、freq(y) ≤ freq(b)。交换 x↔a、y↔b 得 T″：
cost(T) − cost(T″) = (freq(a)−freq(x))(depth(a)−depth(x)) + (freq(b)−freq(y))(depth(b)−depth(y)) ≥ 0
两个因子都非负（频率差 ≥ 0，且 a、b 在最深层故深度差 ≥ 0）。故 cost(T″) ≤ cost(T)，T″ 也最优。∎
(b) Huffman 只在”每个符号必须分配整数位“的框架内最优——即使某符号概率是 0.99，也至少占 1 位。算术编码/ANS 可以给一个符号分配小于 1 位，配合上下文建模效果远好于 Huffman。
(c) DEFLATE（gzip、zip、PNG）、JPEG、以及 zstd 的部分层。原因：解码极快（查表即可），且实现简单、无专利问题。
题 6
(a) 分数背包中"剩余容量"总能被填满，贪心选择不浪费任何容量；0-1 背包中一个选择可能留下用不掉的碎片，局部最优的代价要到很后面才显现。
(b)
容量 10
A: 重 6，价值 30（单位价值 5.0）
B: 重 5，价值 20（4.0）
C: 重 5，价值 20（4.0）
贪心取 A ⟹ 剩容量 4，装不下 ⟹ 30
最优取 B+C ⟹ 40
(c) ① 遗传性：A 独立且 B ⊆ A ⟹ B 独立；② 交换性质：A、B 独立且 |A|<|B| ⟹ 存在 x ∈ B−A 使 A∪{x} 独立。
图的森林：① 森林的任意子集仍是森林 ✓；② 若森林 A 的边数少于森林 B，则 A 的连通分量数多于 B，B 中必有一条边连接 A 的两个不同分量，加入 A 后仍无环 ✓。
(d) 由 Rado-Edmonds 定理，加权拟阵上"按权贪心取（保持独立）“给出最大权独立集。Kruskal 就是在图拟阵上按权（最小）贪心——求最小生成树即在取负权意义下的最大权独立集。∎
活动选择不是拟阵结构：交换性质不成立（两个互不冲突的活动集合，大的那个未必有元素能加进小的那个）。拟阵覆盖的只是"选独立集使权重最大"这一类问题。
(e) 贪心：4+1+1 = 3 枚；最优：3+3 = 2 枚。说明**“贪心在我试的例子上都对"不构成证明**——必须给出交换论证或反例。
题 7
(a) ① 最优子结构；② 重叠子问题。缺少 ② 时用分治（第 28 讲），记忆化没有收益。
(b) 时间 = 状态数 × 每个状态的转移代价。
- LCS：状态 Θ(mn)，转移 O(1) ⟹ Θ(mn)
- 0-1 背包：状态 Θ(nW)，转移 O(1) ⟹ Θ(nW)
(c) 记忆化贴近递归定义、容易写对、只算需要的状态，但常数大、难做滚动数组、有栈溢出风险；递推常数小、缓存友好、易优化空间，但要想清填表顺序。推荐：先写记忆化把逻辑想对，再改写成递推做优化。
题 8
(a)
dp[i][j] = 0 i=0 或 j=0
= dp[i−1][j−1] + 1 X[i−1]==Y[j−1]
= max(dp[i−1][j], dp[i][j−1]) 否则
末尾相同时可直接 +1：由交换论证，存在一个最优 LCS 把这两个末尾字符配对（若某最优解没有配对它们，可以改成配对而长度不减）。
(b) 失去了回溯出具体 LCS 序列的能力（只剩长度）。补救：Hirschberg 算法——分治 + 线性空间 LCS，Θ(mn) 时间、Θ(min(m,n)) 空间，diff 工具用的就是它。
(c) dp[i−1][j] → 删除 A 的第 i 个字符；dp[i][j−1] → 插入 B 的第 j 个字符；dp[i−1][j−1] → 替换。
题 9
(a) 一维滚动后，dp[w] 在被更新前存的是上一行 dp[i−1][w]。
倒序：更新 dp[w] 时 dp[w−wᵢ] 尚未被本轮更新 ⟹ 是 dp[i−1][w−wᵢ] ✓
正序：更新 dp[w] 时 dp[w−wᵢ] 已被本轮更新 ⟹ 是 dp[i][w−wᵢ] ✗（物品被重复取）
正序恰好是「完全背包」（每种物品无限个）的正确写法。
(b) 输入的编码长度是 Θ(n log W)（W 用二进制只需 log W 位）。以输入长度衡量，Θ(nW) = Θ(n·2^{log W}) 是指数级的。这叫伪多项式时间。
(c) 意味着 Θ(nW) 的 DP 并没有"解决” 0-1 背包（它是 NP-完全的）。n=100、W=10⁹ 时 nW = 10¹¹，不可行。应对：① 用 FPTAS（把价值缩放取整后 DP，得 1+ε 近似）；② 分支限界 + 好的上界剪枝；③ 建模成 ILP 交给求解器；④ 检查 W 是否可以按最大公约数缩小。
(d) 把 kᵢ 个同种物品拆成重量为 1, 2, 4, …, 2^j, kᵢ−(2^{j+1}−1) 份的若干个"新物品”，每个做 0-1 背包。任意 0..kᵢ 的取件数都能由这些份的子集和表示，物品数从 kᵢ 降到 O(log kᵢ)。
题 10
(a) 因为"前 i 个的 LIS”无法转移——不知道那个 LIS 以什么值结尾，就无法判断 a[i] 能否接上去。定义成"以 a[i] 结尾"则末尾值明确，可以枚举前驱。代价是最后要在所有 dp[i] 中取最大值。⭐ 通用经验：当"前 i 个的答案"无法转移时，试试"以第 i 个结尾的答案”。
(b) tails[k] = 长度为 k+1 的递增子序列中结尾元素的最小可能值。它必然严格递增，因此可二分。“用更小的值替换"正确的理由：长度不变但结尾更小，将来能接上的元素只多不少——这是一个贪心保持领先的论证。
(c) 不是。 tails 只是各长度的最优结尾值的记录，其中的元素未必在原序列中构成一个子序列。要输出具体序列需额外记录每个元素被放入时的前驱下标。
题 11
(a) 因为长区间的转移依赖短区间（dp[i][j] 由 dp[i][k] 和 dp[k+1][j] 得来，两者都更短）。按长度递增填表才能保证依赖已算好。
(b)
A₁(10×100) A₂(100×5) A₃(5×50)
((A₁A₂)A₃): 10·100·5 + 10·5·50 = 5000 + 2500 = 7500
(A₁(A₂A₃)): 100·5·50 + 10·100·50 = 25000 + 50000 = 75000 差 10 倍
(c) 正向枚举"第一个戳破的"会破坏区间独立性——戳破后左右两段的边界条件互相影响（相邻元素变了）。枚举最后戳破的 k，则 k 一直存在到最后，左右两段 [i,k−1] 和 [k+1,j] 在 k 的两侧独立计算。⭐ 区间 DP 遇到困难时，试试倒过来想。
(d) 平衡树最小化最坏高度；最优 BST 最小化期望深度（按查询频率加权）。后者中高频键应更靠近根，哪怕树不平衡。
题 12
(a)
dp[u][0] = Σ_{v∈children} max(dp[v][0], dp[v][1]) u 不选，孩子随意
dp[u][1] = 1 + Σ_{v∈children} dp[v][0] u 选，孩子都不能选
(b) 树上无环，子树之间完全独立，DFS 一遍即可（Θ(n)）；二分图上由 König 定理 最大独立集 = n − 最大匹配，归结为一次最大流（多项式）；一般图上没有这种结构，最大独立集是 NP-完全的。⭐ 图的结构越受限，问题越容易。
(c) 第一遍（自底向上）求子树大小和以 root 为根的答案；第二遍（自顶向下）由父节点的答案 O(1) 推孩子：
ans[v] = ans[u] − size[v] + (n − size[v])
（根从 u 移到 v：v 子树内的 size[v] 个点各近 1，子树外的 n−size[v] 个点各远 1。）
题 13
(a) dp[mask][i] = 已访问集合 mask、当前在 i 的最短路径。转移 dp[mask|1<<j][j] = min(…, dp[mask][i] + dist[i][j])。复杂度 Θ(2ⁿ·n²)，空间 Θ(2ⁿ·n)。
(b)
| n | n! | 2ⁿ·n² |
|---|---|---|
| 10 | 3.6×10⁶ | 10⁵ |
| 15 | 1.3×10¹² | 7×10⁶ |
| 20 | 2.4×10¹⁸ | 4×10⁸ |
| 25 | 1.6×10²⁵ | 2×10¹⁰（且内存 6.7 GB） |
(c) mask & (mask-1) = 清掉最低位的 1；mask & (-mask) = 取出最低位的 1（lowbit）。
(d) 每个元素有三种状态：不在 mask 中、在 mask 但不在 sub、在 sub 中。故 Σ_{mask} 2^{|mask|} = 3ⁿ。
(e) tight 状态表示"当前前缀恰好等于上界的前缀”，它的结果依赖具体的上界前缀，不同的 n 会给出不同的值。缓存它会导致跨实例的错误复用。（除非把上界前缀也编进缓存 key。）
题 14
(a) π[i] = P[0..i] 的最长真前缀长度，且该前缀同时是 P[0..i] 的后缀。
P: a a b a a a b
i: 0 1 2 3 4 5 6
π[i]: 0 1 0 1 2 2 3
(b) 当前 border（长 k）用不上时，退到"border 的 border"——即 π[k−1]。这本身是递归结构：一个串的所有 border 构成一条由 π 串起来的链。
(c) 取 Φ = k（当前匹配长度）。外层每次迭代 k 最多 +1（总增量 ≤ n）；内层每次迭代 k 严格减少（π[k−1] < k）。由于 k ≥ 0，内层总次数 ≤ 总增量 ≤ n。故 Θ(n)。构造 π 同理 Θ(m)。∎
(d) 完全相同的论证模式：一个量只能有限次地增加，因此它减少的总次数也有限。单调栈是"每个元素进出各一次"，KMP 是"k 的总增量有界"。⭐ 认出这个模式，很多看似 O(n²) 的循环都能证明是 O(n)。
题 15
(a) new = ((old − s[i]·b^{m−1})·b + s[i+m]) mod p。必须验证是因为哈希碰撞会导致误报——不同字符串可能有相同哈希值。
(b) 多模式匹配：查找 k 个等长模式时，把它们的哈希放进一个集合，扫一遍文本即可（Θ(n + Σ|Pᵢ|)），而 KMP 要跑 k 遍。另外二维模式匹配、rsync 分块同步也用它。
(c) Trie 的查找沿着字符逐层下降，深度 = 字符串长度 L，与 Trie 中有多少单词无关。相比散列表多了：① 前缀查询（自动补全、最长前缀匹配）；② 在第一个不匹配的字符就能返回，而散列表必须算完整个字符串的哈希。
(d) 文本固定、模式多变 → 预处理文本（后缀数组/后缀自动机）；模式固定、文本流式 → 预处理模式（KMP / AC 自动机）。
题 16
(a) P = 存在多项式时间求解算法的判定问题；NP = 存在多项式时间验证 yes 答案的问题。“N” = Nondeterministic（非确定性图灵机的多项式时间），不是 Non-Polynomial。
(b) A ≤_p B（把已知难的 A 归约到待证的 B）。因为这说明"能解 B 就能解 A"，故 B 至少和 A 一样难。反方向什么也证明不了。⭐ 口诀：把「已知很难的问题」变成「你的问题」。
(c) SAT 是 NP-完全的。证明思路：任何 NP 问题都有多项式时间验证器，验证器的计算过程可用布尔电路模拟、编码成 SAT 公式。它是第一个被证明的 NPC 问题，是整棵归约树的根——有了它，其他所有 NPC 问题都可通过归约链得到。
(d) (⟸) 设 G 中有大小为 m 的独立集 I。每个子句三角形内部两两相邻，故 I 在每个三角形中至多取 1 个顶点；共 m 个三角形、|I| = m ⟹ 恰好每个三角形取 1 个。互补边（x 与 ¬x 之间）保证 I 中不会同时含 x 和 ¬x，因此可以一致地把 I 中的文字全部赋为真（其余任意）。于是每个子句都有一个真文字，公式可满足。∎
(e) 问题的难度对表述极其敏感，不能靠直觉判断。 一字之差（最短/最长、每条边一次/每个点一次、2-SAT/3-SAT）就可能跨越 P 与 NPC 的边界。
题 17
(a) 算法：反复任取一条未被覆盖的边，把它的两个端点都加入覆盖集，删掉所有与这两点关联的边。
证明：算法选出的边构成一个匹配 M（两两不共享顶点，因为选完就删掉了关联边）。任何顶点覆盖必须覆盖 M 中的每一条边，而 M 中的边两两不共享顶点，故任何覆盖至少需要 |M| 个顶点，即 OPT ≥ |M|。算法用了 2|M| 个顶点，故 ALG = 2|M| ≤ 2·OPT。∎
(b) 不意味着。 “NP-完全"是关于最坏情况的论断。真实实例往往有结构，不是最坏情况：SAT 求解器靠 CDCL（冲突驱动子句学习）、VSIDS 启发式、单元传播、重启策略等，在结构化实例上表现远好于最坏界。工业界每天在求解理论上"不可解"的问题。
(c) ① 近似算法（有可证明的质量保证）；② 参数化算法（f(k)·poly(n)，把指数隔离在小参数里）；③ 精确的指数算法（分支限界、SAT/ILP 求解器）；④ 启发式/元启发式（无保证但实践够用）；⑤ 改变问题（利用输入结构、放松需求）。
(d) ① 树/树宽小 ⟹ 最大独立集、支配集等在树上是线性的（树形 DP）；② 二分图 ⟹ 独立集、顶点覆盖归结为最大匹配（König 定理）；③ 平面图 ⟹ 有 PTAS，4-着色一定可行；④ 数值范围小 ⟹ 背包、子集和的伪多项式 DP 可用。
(e) 因为很多"NP-难"是被过度精确的需求逼出来的。业务上"好解"和"最优解"的差别可能只有 2%，但计算代价差 1000 倍；或者一个约束（“最多恰好 3 个”）稍微放松（“最多 5 个”）就让问题落入 P。在动手写算法之前，回去确认"是不是真的需要最优解”，常常能省掉全部麻烦。