企业官网建设流程全解析

1. 先把这门课的期末考“地图”画出来

算法设计与分析的期末复习，最忌讳的一件事就是一上来抱着教材从第一章啃到最后一章。我带过几届学弟学妹的考前突击，也自己踩过一轮完整的坑，最大的体会是：这门课的考点密度极不均匀，复习的收益差距可以拉开好几倍。同样花十个小时，有人从及格冲到优秀，有人还在递归式的下标上纠结。差别不在于聪不聪明，而在于有没有先搞清楚“考什么、怎么考、我该先补哪块”。

先说这门课的本质。算法设计与分析不是让你背代码，它考的是三件事：会不会算复杂度、会不会选策略、会不会证明正确性。三个能力对应三种题型，也对应三条完全不同的复习路径。复杂度是地基，任何一道题都可能让你写一个递推式；策略是主干，分治、动态规划、贪心、回溯、分支限界这五板斧几乎撑起全部设计题；证明是分水岭，是普通同学和拿高分同学之间最大的差距。

网络热搜里反复出现的“湘潭大学算法设计与分析”“算法设计与分析期末编程题”“算法设计与分析期末题”，其实指向同一个痛点：大家最怕的是编程题和设计题，而不是选择题。因为选择题勾错了损失两分，编程题写不出来可能直接损失十几分。所以我这份复习笔记的权重分配是：复杂度分析和策略选择占六成，编程实现占三成，证明套路占一成——但那一成往往是决定能不能上 90 分的部分。

下面我会按“题型拆解 → 复杂度地基 → 五板斧逐个击破 → 代码模板 → 踩坑速查”的顺序往下讲。不管你基础如何，建议至少把第 2 节和第 4 节读透，这两块是性价比最高的。

1.1 题型分布与分值权重的真实拆解

不同学校的卷面结构差异挺大，但底层逻辑是相通的。我把它归成五类，并给出我观察到的常见权重范围：

这张表你最好抄下来贴在复习计划本第一页。它的用法是：当时间不够时，优先保“算法设计题”和“计算分析题”，因为这两块确定性最强、训练见效最快。选择题靠临考前几天刷概念就够了，证明题则要在策略题练熟之后再回头补，因为证明用的工具（交换论证、归纳、归约）本身就以策略理解为前提。

还有一个容易被忽略的点：计算分析题是唯一可以“无脑得分”的题型。写递推式、套主定理、画递归树，这些都是机械动作，练二十道就能形成肌肉记忆，考场上几乎不会失分。而设计题需要一点灵感和经验积累，证明题更是看临场发挥。所以复习节奏应该是：先用计算题建立信心和手感，再攻设计题，最后扫证明题和概念题。

1.2 复习顺序的取舍逻辑

我个人的建议顺序是：复杂度分析 → 动态规划 → 分治 → 贪心 → 回溯与分支限界 → 图算法 → NP 理论 → 概念扫尾。这个顺序不是教材顺序，而是按“出现频率 × 学习曲线”排的。

动态规划为什么排这么前？因为它出现的频率最高，而且和贪心、分治都有交叉，是整门课的枢纽。把 DP 吃透，你再看贪心就知道“为什么这里不能用 DP 而能用贪心”，再看分治就知道“为什么这个递归式能合并”。分治排第三是因为它的数学建模（递归式）和复杂度分析直接打通，学完第一二节马上就能练手。

回溯和分支限界放在后面，是因为它们在期末里通常只出一道题，而且框架固定，背模板就能拿分，性价比属于“后期补分”型。NP 理论排最后，是因为它抽象、容易混淆概念，但考法固定（判定 P/NP/NPC，或者做一次简单归约），不需要太多前置积累。

提示：如果你只剩三到五天，把动态规划、分治、贪心这三块的核心例题各刷三遍，性价比远超平均用力。

2. 渐进复杂度分析：所有题的地基

这一节是整门课的地基。我发现很多同学做题卡壳，不是不会设计算法，而是写不出递推式、算不出复杂度，导致明明思路对了却拿不到分。复杂度分析其实是一门“手艺”，有固定的判定流程和套路。

渐进符号一共五个，考试里真正高频用的是 O、Ω、Θ 三个，o 和 ω 偶尔出现在概念题里。它们的定义必须能背能推：O 是上界，Ω 是下界，Θ 是紧确界，o 是严格上界，ω 是严格下界。考试里最常用的判定手法是取极限：算 f(n)/g(n) 当 n 趋于无穷时的值，是常数就 Θ，是无穷就 ω 方向，是零就 o 方向。

常见函数阶的排序必须闭着眼都能排出：常数 < log n < n^0.5 < n < n log n < n² < n³ < 2^n < n! < n^n。别小看这个排序，选择题里“下列函数中增长最快的是”这种题，只要你记得住就秒答。有个口诀式记忆法：“对数不如幂，幂不如指数，指数不如阶乘”，反过来把幂的指数从小到大排就成。

2.1 主定理三种情况的判断手法

主定理是求递归式渐进阶最省力的工具，但很多人用错，根本原因是没搞清“比较对象”。递归式形如 T(n) = a·T(n/b) + f(n)，其中 a ≥ 1，b > 1，f(n) 是渐近正的函数。关键是拿 f(n) 和 n^(log_b a) 做比较：

• 情况一：f(n) = O(n^(log_b a − ε))，说明递归部分占主导，则 T(n) = Θ(n^(log_b a))。
• 情况二：f(n) = Θ(n^(log_b a) · log^k n)，则 T(n) = Θ(n^(log_b a) · log^(k+1) n)。k=0 时就是 Θ(n^(log_b a) · log n)。
• 情况三：f(n) = Ω(n^(log_b a + ε))，且满足正则条件 a·f(n/b) ≤ c·f(n)（c<1），则 T(n) = Θ(f(n))。

举个必考例子：归并排序 T(n) = 2T(n/2) + n。这里 a=2，b=2，n^(log_2 2) = n，f(n) = n，两者同阶，属于情况二（k=0），所以 T(n) = Θ(n log n)。再看二分查找 T(n) = T(n/2) + 1，a=1，b=2，n^(log_2 1) = n^0 = 1，f(n)=1，同阶，情况二，T(n)=Θ(log n)。

正则条件是情况三最容易漏的地方。比如 T(n) = 2T(n/2) + n²，n^(log_2 2)=n，f(n)=n² 明显大于 n，属于情况三，验证正则条件：2·(n/2)² = n²/2 ≤ c·n²，取 c=0.5 成立，所以 T(n)=Θ(n²)。但如果 f(n) 增长得太“不规律”，主定理就不适用了，这时候要退回递归树或者代入法。

2.2 递归树的画法与代入法验证

主定理不适用的时候（比如神秘的 T(n)=T(n/3)+T(2n/3)+n），递归树是万能解法。画递归树的步骤是：每层列出该层所有子问题的代价之和，然后求和所有层的代价。

以 T(n)=T(n/3)+T(2n/3)+n 为例。第一层代价 n，第二层子问题规模 n/3 和 2n/3，代价和还是 n，第三层依然是 n……关键是看树什么时候停。最深的路径是沿 2n/3 这条分支，每次乘 2/3，直到降到常数，深度是 log_{3/2} n。所以总共约 log_{3/2} n 层，每层代价 n，T(n)=O(n log n)。这个用主定理算不了，但递归树一眼就看出来。

代入法用来“验证你猜的答案”。步骤是先猜一个阶，再用数学归纳法证明。比如猜 T(n)=O(n log n)，假设对所有小于 n 的规模成立，代入 T(n)=2T(n/2)+n ≤ 2·c·(n/2)·log(n/2)+n = cn·log n − cn + n ≤ cn·log n（当 c ≥ 1 时），归纳成立。考场上如果时间紧，代入法写个框架也能拿过程分。

2.3 复杂度分析里最常踩的四个坑

第一个坑：把循环变量的变化方向搞反。比如for(i=1; i<=n; i*=2)是 O(log n)，但很多同学写成 O(n)。判断标准是“循环体执行次数”，不是“n 的大小”。看到乘法或除法递进，一律往 log 想；看到加减递进，往 n 想。

第二个坑：嵌套循环直接相乘。两层独立循环确实是 n×n，但如果内层循环依赖外层的变量（比如 j 从 i 开始），就要做求和而不是相乘。经典例题for(i=1;i<=n;i++) for(j=1;j<=i;j++)的总次数是 1+2+...+n = n(n+1)/2 = O(n²)，看着像相乘，其实要精确求和才能拿到满分。

第三个坑：把 log 的底数当回事。log₂ n 和 log₁₀ n 只差常数倍，在渐进符号下是同一个阶。所以答题时写 Θ(log n) 就够，不用纠结底数，除非题目明确要求具体数值。

第四个坑：忽略最好/最坏/平均的区别。快排最好 O(n log n)、最坏 O(n²)、平均 O(n log n)，考场上问“快速排序的时间复杂度”一定要答三段，只写一个可能被扣分。同理，二分查找在有序数组上是 Θ(log n)，但在链表上因为随机访问代价是 Θ(n)，这个边界也要分清。

注意：主定理只适用于 T(n)=aT(n/b)+f(n) 这种“均匀划分”的形式。如果子问题规模不相等（如 T(n)=T(n−1)+T(n−2)），主定理无效，必须用递归树或特征方程。

3. 分治法：从归并排序到最近点对

分治法是五大策略里最“数学”的一个，因为它和递归式、复杂度分析天然咬合。分治的核心思想是把大问题拆成规模更小的同型子问题，分别求解后合并。它的三步走是：Divide（划分）、Conquer（解决）、Combine（合并）。听起来简单，但考场上真正难的是“怎么划分才能让合并这一步高效”。

判断一道题能不能用分治，看两个信号：一是问题能自然二分（数组、平面点集、矩阵），二是子问题的解能在线性或接近线性时间内合并成原问题的解。如果合并代价太高（比如 O(n²)），分治反而比暴力慢，这也是很多人误用分治的地方。

3.1 分治递归式的建模方法

分治算法的复杂度几乎都能写成 T(n) = a·T(n/b) + f(n) 的形式，其中 a 是子问题个数，b 是规模缩小的倍数，f(n) 是划分和合并的代价。建模的关键是数清楚 a 和 b。

归并排序：每次二分成两个 n/2 的子问题，合并需要 O(n) 的辅助数组操作，所以 T(n)=2T(n/2)+n。二分查找：只递归一侧，a=1，b=2，比较代价 O(1)，所以 T(n)=T(n/2)+1。快速排序平均情况下和归并类似，但划分代价 O(n)、递归两边（平均各 n/2），所以平均 T(n)=2T(n/2)+n。

有个特别好用的小技巧：先写出 a、b、d（f(n) 的次数），再套一张简化判定表。当 f(n)=n^d 时：

这张表其实就是主定理的简化版，专门对付 f(n) 是幂函数的情况，考场上比背完整主定理更快。

3.2 五个分治经典例题拆解

归并排序是分治的“Hello World”。要点是合并函数 merge：两个已排序子数组，双指针比较取小。归并的稳定性来自“相等时取左边”，这个细节在问“哪些排序稳定”时是得分点。它的递归树高度 log n，每层合并总代价 n，所以 Θ(n log n)，空间 O(n) 是它的软肋。

最大子段和的分治解法是高频设计题。把数组从中间劈开，最大子段要么全在左半、要么全在右半、要么跨越中点。前两种递归求解，第三种从中点向两边各扫一遍求最大后缀和与最大前缀和，代价 O(n)。所以 T(n)=2T(n/2)+O(n)=O(n log n)。这里要特别注意：分治解法不是最优的，DP 可以做到 O(n)，考试里如果题目问“最优”，要答 DP；如果问“用分治设计”，再写分治。

最近点对问题是分治里最优雅的例子，也是典型的“合并比划分难”。按 x 坐标排序后二分，左右各求最近距离 d₁、d₂，取 d=min(d₁,d₂)。关键在于跨中线的点对：只需考虑中线左右各宽 d 的带状区域，且区域内每个点最多与后面 7 个点比较（鸽巢原理保证），所以合并代价 O(n)。整体 T(n)=2T(n/2)+O(n)=O(n log n)。这里的“最多比 7 个点”是常考的证明细节，一定要能说清为什么是常数个。

棋盘覆盖考的是分治的构造思路。2^k × 2^k 的棋盘有一个特殊格，用 L 型骨牌覆盖其余。做法是把棋盘四等分，特殊格所在的那块继续递归，另外三块的角上用一块 L 型骨牌人为制造“特殊格”，于是四个子问题都有特殊格。递归式 T(n)=4T(n/2)+O(1)，注意这里的 n 是边长，解得 O(n²)，正好等于骨牌数。

快速排序的随机化版本也是分治，但它的复杂度分析要用到期望。随机选主元保证期望划分平衡，期望复杂度 O(n log n)。这个和确定性快排的“最坏 O(n²)”形成对比，是选择题的常客。

我的实操心得：分治的递归式建模不要急着套主定理，先把 a、b、f(n) 写在草稿纸上，数错了后面全错。尤其是“子问题个数”a，棋盘覆盖里 a=4 不是 2，最近点对里合并前是 a=2，这些细节决定成败。

4. 动态规划：状态定义才是命门

如果整门课只能复习一块，我选动态规划。它出现频率最高、题型最多变、也最能拉开分差。DP 的两大前提是最优子结构和重叠子问题：最优子结构决定“能不能用 DP”，重叠子问题决定“用了才划算”。很多人分不清 DP 和分治，一句话概括：分治的子问题相互独立不重叠，DP 的子问题重叠需要记录。没有重叠还硬用 DP，那就退化成普通递归，白搭。

DP 的复习有个反直觉的真相：写状态转移方程只是最后一步，真正的功夫在状态定义上。状态定义错了，方程怎么写都不对；状态定义对了，方程几乎是自然涌现的。所以练 DP 的正确姿势是先问自己三个问题：状态表示什么？状态之间怎么转移？边界和答案在哪？

4.1 从暴力递归到 DP 的三步推导

我强烈推荐用“三步推导法”练 DP，考场上也按这个顺序答题，过程分稳稳的。

第一步，写暴力递归。先不考虑效率，直接按问题定义写递归函数。比如 0-1 背包，定义 f(i, c) 表示“前 i 件物品、容量为 c 时的最大价值”，那么 f(i,c) = max(f(i−1,c), f(i−1,c−w_i)+v_i)，边界是 i=0 时返回 0。这一步哪怕指数级也要写出来，因为它是后面两步的骨架。

第二步，加记忆化。把递归函数改成带备忘录的版本，用数组或哈希表缓存已经算过的 (i,c)。这一步只是把重叠子问题“记住”，复杂度立刻从指数降到状态数乘以转移代价。

第三步，改成递推（填表）。把记忆化递归转成自底向上的循环，按依赖顺序填表。这一步的意义是消除递归开销、方便做空间优化。答题时写递推版本更规范，老师也更认可。

这三步看着简单，但它是应对“从没见过的新 DP 题”的最强武器。考场上遇到陌生题，不要慌着找记忆里类似的题，直接按这三步硬推，八成能推出正确方程。

4.2 高频 DP 题清单与状态方程

下面这张表是我整理的期末高频 DP 题，覆盖八成以上的设计题场景：

这张表的价值在于：它把“状态定义”和“转移方向”一起给你了，很多同学方程写对了却因为循环方向错误（0-1 背包里正序还是逆序）而丢分。记住一个口诀：0-1 背包逆序，完全背包正序。逆序是为了保证每件物品只用一次，正序则允许重复使用。这个细节几乎每年都有人栽。

区间型 DP（矩阵连乘、石子合并）的套路是枚举区间长度，再枚举断点。外层循环是区间长度 len 从 2 到 n，中层是起点 i，内层是断点 k。这个三层循环的顺序千万不能乱，因为大区间依赖小区间的结果，必须按长度递增填表，否则取到的是还没算的值。

4.3 空间优化的思路与边界

DP 的空间优化是进阶技巧，也是区分度所在。核心思想是观察转移只依赖哪些层：如果 f[i] 只依赖 f[i−1]，就能把二维压成一维；如果依赖 f[i−1] 和 f[i]，就用两个变量或两行滚动。

0-1 背包的经典压缩：把 f[i][c] 压成 f[c]，然后在容量维度逆序遍历。为什么逆序？因为逆序保证你用到的是“上一轮（未更新）的 f[c−w]”，如果正序就会用到本轮已经选过的 f[c−w]，等于允许重复选，那就变成完全背包了。这是空间优化里最容易搞错的方向问题。

LIS 的 O(n log n) 优化是个亮点：用一个数组 d，d[k] 表示长度为 k 的递增子序列的最小结尾元素。遍历每个元素时二分查找它在 d 中的位置替换。这个技巧考得不多但很出彩，写出来能加分。

提示：空间优化不是必须的，考场上如果时间紧、状态没把握，老老实实写二维版本，正确性优先。宁可多花 O(n) 空间，也不要为了炫技压错维度导致全盘皆输。

5. 贪心与回溯：两条相反的思路

贪心和回溯是这门的“两极”。贪心一条路走到黑、不回头的乐观派；回溯是每条路都试探、走不通就回退的谨慎派。它们经常被放在一起考，就是让你判断“这道题该乐观还是该谨慎”。

5.1 贪心正确性证明的两个套路

贪心的可怕之处在于：它能求出一个解，但这个解不一定是最优的。所以凡是问“能否用贪心”，你必须先证明贪心选择性质。期末考最常用的两个证明套路是交换论证法和数学归纳。

交换论证法是证明贪心的标准武器。思路是：假设存在一个最优解，如果它的第一步选择和贪心选择不同，那么我们通过交换把它的第一步换成贪心选择，证明解不会变差。由于每一步都能交换，最终这个最优解就变成了贪心解，从而贪心解就是最优解。

以活动安排问题为例：贪心策略是每次选结束时间最早的活动。证明时假设最优解的第一个活动是 a，贪心的第一个是 b（b 结束更早）。因为 b 结束更早，把 a 换成 b 后剩下的活动时间不会更紧，所以解不会变差。经典题目像哈夫曼编码、最小生成树（Prim、Kruskal）、单源最短路径（Dijkstra）都靠这套证明。

什么题不能用贪心也是必考。0-1 背包就是经典反例：按单位价值贪心会出错。举个具体例子，背包容量 10，物品 A 重 6 价值 6（单位价值 1），物品 B、C 各重 5 价值 5（单位价值也是 1）。贪心先取 A，剩 4 装不下 B 或 C，总价值 6；但最优是取 B、C，总价值 10。所以 0-1 背包必须 DP。而分数背包（物品可切分）就能用贪心，因为可以切一部分凑容量，没有“装不下就浪费”的问题。这个对比是高频考点，务必记牢。

5.2 回溯法的框架与剪枝技巧

回溯法的本质是在解空间树上做深度优先搜索。它的通用框架非常固定：

def backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 选择列表: if not 可行(选择): # 剪枝 continue 做选择 backtrack(路径, 选择列表) 撤销选择 # 关键：回溯

这个框架的核心是“做选择”和“撤销选择”成对出现，保证进入下一层时状态干净。很多同学写回溯忘了撤销，导致答案错乱，是经典失误。

回溯的效率完全靠剪枝。剪枝分两类：可行性剪枝（当前部分解已经违反约束，直接剪）和限界剪枝（当前部分解已经不可能优于已知最优解，直接剪）。N 皇后问题里，剪枝条件是“同列、同对角线不能有皇后”；子集和问题里，如果当前和已经超过目标就剪枝。写了剪枝的回溯和没写的，性能可能差好几个数量级，考试里明确要求剪枝的题一定要写上，不然即使答案对也被扣分。

经典回溯题清单：N 皇后、子集和、图着色、哈密顿回路、迷宫路径、数独。它们的共同点是解空间树是中序或排列树，元素不能重复使用（所以需要 visited 标记）。这里有个易混点：遍历所有排列用排列树，遍历所有子集用子集树。排列树每个节点有 n−k 个分支，子集树每个节点有“选/不选”两个分支，复杂度分别是 O(n!) 和 O(2^n)。

5.3 分支限界与回溯的区别

分支限界经常和回溯一起考，但两者的搜索方式不同。回溯是深度优先（栈/递归），分支限界是广度优先或优先队列（队列/堆）。回溯用“剪枝”砍掉不可能的分支，分支限界用“限界”估算每个节点的上界或下界，优先扩展最有希望的节点。

最大团问题、旅行商问题（TSP）、0-1 背包的优化版本常用分支限界。考试里如果题目要求“用分支限界法”，你要写出限界函数（bound function），这个函数的松紧程度直接决定算法效率。限界函数越紧，剪枝越狠，但也越难设计，这中间的权衡是设计题可以发挥的地方。

6. 图算法与 NP 完全性：两大理论板块

图算法和 NP 理论是期末里两个比较“独立”的板块。图算法偏实现和计算，NP 理论偏概念和形式化推理。它们的分值通常加起来占到三四成，但复习方式完全不同。

6.1 图算法的必考三件套

最小生成树考 Prim 和 Kruskal 两个算法。Prim 从点出发，适合稠密图，用邻接矩阵加数组维护最小权值，复杂度 O(n²)；Kruskal 从边出发，适合稀疏图，用并查集加边排序，复杂度 O(e log e)。两者都是贪心，证明都用切割性质。选择题常问“稠密图用哪个”，答案是 Prim。

单源最短路径的核心是 Dijkstra、Bellman-Ford、Floyd 三兄弟。Dijkstra 是贪心，不能处理负权边，用优先队列优化后 O((n+e) log n)；Bellman-Ford 是动态规划，能处理负权边、能检测负环，复杂度 O(n·e)；Floyd 是全源最短路，三重循环枚举中转点，O(n³)。这里有个经典易错点：Floyd 的中转点 k 必须是最外层循环，因为它是按“允许经过前 k 个点”的阶段划分的，写错循环顺序结果会错。

网络流考最大流最小割定理。Ford-Fulkerson 是基础框架，Edmonds-Karp 用 BFS 找增广路保证 O(n·e²)，Dinic 用分层图更快。考试里通常考“求最大流并找出最小割”，你只要会画残量网络、反复找增广路就行，不需要写复杂代码。

6.2 NP 完全性证明的归约套路

NP 理论是很多人头疼的部分，但它的考法极其固定。核心概念必须区分清楚：P 是多项式时间可解的问题，NP 是多项式时间可验证的问题，NPC 是 NP 中最难的一类，NPH 是至少和 NPC 一样难的所有问题。注意 P ⊆ NP 是确定的，但 P 是否等于 NP 至今未知。

证明一个问题是 NPC 分两步：先证明它属于 NP（给出一个多项式时间的验证算法），再选一个已知 NPC 问题归约到它（比如从 3-SAT 或顶点覆盖归约）。归约的意思是：把已知问题的任意实例，在多项式时间内转换成新问题的实例，使得新问题有解当且仅当原问题有解。

常见的归约链条是：SAT → 3-SAT → 团问题 / 顶点覆盖 / 哈密顿回路 → TSP。考试里通常让你做一步简单归约，比如“证明顶点覆盖是 NPC”，你只需要说清楚归约怎么构造、证明对应关系、说明多项式时间即可。

注意：判定问题时别把 P 和 NP 说反了。很多人直觉觉得 NP 是“非多项式”，其实 NP 是“非确定性多项式时间可解”，也就是多项式时间可验证。这个概念题几乎每年都出。

6.3 近似算法与下界的思想

NP 难问题无法在多项式时间内求最优解，于是有了近似算法。评价近似算法用近似比：算法解不超过最优解的 ρ 倍。比如顶点覆盖有 2-近似算法，TSP 在满足三角不等式时有 1.5-近似。期末里如果考到“设计一个近似算法并分析近似比”，写出贪心策略和比值分析就够了。

另一类常考的是下界证明，主要用于排序问题。基于比较的排序下界是 Ω(n log n)，证明用的是决策树：n 个元素的排列有 n! 种，决策树至少要有 n! 个叶子，二叉树的深度至少是 log(n!) = Θ(n log n)。这个证明每年必考，务必背下来。

7. 编程题实战：模板与手写细节

编程题是很多人最紧张的部分，尤其是“算法设计与分析期末编程题”这个热搜词，说明大家普遍在这栽跟头。我的建议是：不要指望临场从零构思，而是提前准备一套能套用的模板，考场上根据题意微调。

7.1 必背代码模板

归并排序与合并是编程题的基础，很多题（求逆序对、稳定性排序）都基于它：

def merge_sort(a, l, r): if l >= r: return mid = (l + r) // 2 merge_sort(a, l, mid) merge_sort(a, mid + 1, r) i, j, tmp = l, mid + 1, [] while i <= mid and j <= r: if a[i] <= a[j]: # 取等号保证稳定 tmp.append(a[i]); i += 1 else: tmp.append(a[j]); j += 1 tmp.extend(a[i:mid+1]) tmp.extend(a[j:r+1]) a[l:r+1] = tmp

求逆序对只需在a[i] > a[j]时累加mid - i + 1，这是经典变形。

二分查找的三个版本必须分清：找目标值、找左边界、找右边界。考场上最常见的错误是死循环，根源是while l < r还是while l <= r、mid要不要加一没搞清。记忆口诀：找左边界用mid = (l+r)//2，找右边界用mid = (l+r+1)//2，这样能避免死循环。

0-1 背包的一维写法：

def knapsack(w, v, C): n = len(w) f = [0] * (C + 1) for i in range(n): for c in range(C, w[i] - 1, -1): # 逆序！ f[c] = max(f[c], f[c - w[i]] + v[i]) return f[C]

回溯的 N 皇后框架建议背到能默写，因为它的“做选择—递归—撤销”结构是通用套路。

7.2 手写代码的考场细节

机试和手写代码的评分点不完全一样。手写代码时，老师看的是思路和边界，不是能不能编译通过。所以手写时一定要：写清楚函数签名和参数含义；标注关键步骤的注释；处理边界（空数组、单个元素、越界）；写出复杂度。

如果是机试，除了正确性还要注意输入输出格式。很多同学算法对了却因为没按题目格式读入多组数据而全盘皆输。建议机试前把输入模板练熟，比如while True: try: ... except EOFError: break处理不确定组数、n, m = map(int, input().split())处理一行多值。

我的踩坑记录：有次机试题目是“多组测试数据直到文件结束”，我按单组写的，结果第三个测试点就挂了。从那以后我养成了习惯——先看输入描述里的“多组”“直到 EOF”这些关键词，再决定读入方式。

8. 常见问题与排查速查

最后这部分是我认为整篇最有价值的。下面这些坑，要么是我自己踩过的，要么是看过别人踩的，整理成速查表方便你考前扫一遍。

关于复习时间安排，我的经验是：别平均分配。考前一周，用两天刷复杂度分析和分治，两天主攻动态规划，一天搞贪心和回溯，一天扫图算法和 NP，最后一天专门背模板和看错题。这样安排的原因是前两块确定性强、见效快，DP 分值最高，后面几块靠模板能保底。

还有一点想提醒：错题比新题重要得多。期末复习阶段最忌讳疯狂刷新题却从不回头看。我建议准备一个错题本，只记“我为什么错”这一句话，考前翻一遍，能避免的失分比多刷十道题都多。

另外，考试时遇到完全没思路的设计题，别空着。写出你能想到的暴力解法、分析它的复杂度、说明瓶颈在哪、给出优化方向，这样即使没写出最优解，过程分也能拿不少。老师们普遍对“有分析过程的部分解”给分不低，而对空白卷只能给零分。这个策略我在好几门算法课上用过，屡试不爽。

至于证明题，如果实在推不出来，至少把定义和思路框架写出来。比如证明贪心，先写“我尝试用交换论证法”，再写“假设存在最优解使得第一个选择不同于贪心”，把开头这几句写上，后面哪怕不完整，老师也知道你懂套路，通常会给步骤分。空着是绝对不划算的。