吉林大学《算法分析与设计》这门课历年期末和考研复试里第五道大题都是公认的“分水岭”。前面几道题考的是基础套路背一背、练一练基本能拿分到了第五题出题人开始动真格了——要么把多个算法揉在一道题里要么给你一个从没见过的场景让你现场建模。我当年复习的时候在这道题上栽过跟头后来把近几年的真题、期末卷和辅导书里的相关题目翻来覆去啃了好几遍才算摸清了它的脾气。这篇文章就把我整理的第五道大题的算法题汇总、解题套路和避坑经验一次性分享出来。不管你是正在准备期末考试还是在为复试机试刷题只要把里边的题型和模板吃透第五道大题至少不会拖后腿。1. 第五道大题到底在考什么题型解析与出题规律先说结论吉大的第五道大题几乎从不考单一知识点。它喜欢把两到三个算法放在同一个题目背景里考察你能不能根据数据范围和题目条件选出正确的算法组合并且能写出正确的状态转移、贪心策略或搜索剪枝条件。1.1 高频考点分布我统计了近五年的期末题和回忆版真题第五道大题的考点分布大致如下考点方向出现频率典型问法动态规划尤其区间DP和树形DP★★★★★求最大值/最小值/方案数图论算法综合最短路最小生成树★★★★先求最短路再在路径上构建生成树贪心算法与排序策略证明★★★☆给出贪心规则并证明正确性字符串匹配KMP/扩展KMP★★★☆求字符串循环节、最长公共前缀二分答案判定函数★★★最小化最大值/最大化最小值DFS/BFS剪枝搜索★★☆求可行方案数或搜索最优解这里特别要提醒动态规划出现频率最高但很少单独考“裸DP”。出题老师通常会给一个实际问题比如“给定一段DNA序列求最少修改几次才能使其不存在某个连续子串”这类题目表面上是字符串题实际上是用DP做状态机匹配。1.2 第五道大题的三个典型特征第一是数据范围会给得很暧昧。题目不会直接告诉你用哪种算法但通过数据范围能推断——n在10^3量级基本就是O(n²)的DP或Dijkstran在10^5量级多半需要O(nlogn)的贪心或二分答案n在20以内则可以考虑状压DP或爆搜剪枝。读题第一步永远是看数据范围这是所有算法题的第一准则。第二是输出要求经常是“双结果”。比如既要输出最大收益又要输出选择方案既要输出最短路径长度又要输出具体路径。很多人只顾着算值忘了回溯输出方案白白丢分。平时练习就应该养成路径记录的习惯。第三是题目背景常和专业结合。吉大计算机学院的算法课有个特点喜欢在生物信息、图像处理、网络路由这些方向出背景题。这里不存在真正的领域知识壁垒题目其实已经把模型抽象好了但如果你不看穿这层背景很容易被五花八门的描述绕晕。2. 核心算法模板与解题套路从暴力到最优的思路演进每次收到学生私信问我第五道大题怎么准备我的建议都一样别急着刷难题先把每个经典算法的模板敲到肌肉记忆的程度。第五道大题不是考你灵光一现而是考你在有限时间里稳准狠地写出正确的代码。2.1 动态规划先写暴力递归再改记忆化动态规划说难很难说简单也简单——它本质上是暴力搜索的“去重版”。我在解DP题时有个死习惯第一步先把递归版本的暴力解写出来哪怕复杂度是O(2^n)。代码如下// 暴力递归以“最长递增子序列长度”为例 int dfs(int i) { int res 1; for (int j 0; j i; j) { if (nums[j] nums[i]) { res max(res, dfs(j) 1); } } return res; } // 主函数里对每个i调用 dfs(i)取最大值然后第二步观察递归函数的状态参数有哪些。如果状态只有两三个整数变量十有八九能改成DP。改记忆化只需要加一个数组int memo[1005]; int dfs(int i) { if (memo[i] ! -1) return memo[i]; int res 1; for (int j 0; j i; j) { if (nums[j] nums[i]) { res max(res, dfs(j) 1); } } return memo[i] res; }从暴力递归改成记忆化代码改动量很小但在考场上能帮你理清思路。如果题目要求输出具体方案就在状态转移时用path数组记录“我这一步是从谁转移来的”最后递归回溯打印即可。区间DP和树形DP也都遵循这个逻辑只是状态定义更复杂一些。关于状态定义我有一个血泪心得如果一道题你卡了十分钟还定义不出合适的状态十有八九是状态定义漏了信息。比如“前i个物品中选若干个”不够用时想想是否应该加一维“当前容量”或“当前已选数量”。DP的维度不是越多越好但少了绝对推不动状态转移。2.2 贪心算法正确性证明是得分关键贪心最大的陷阱是“感觉对实际上不对”。第五道大题考贪心时通常有一个小问是“证明贪心策略的正确性”。这个一定要写不写直接扣分。贪心证明的常规套路有三种。第一种是交换论证法——假设存在一个最优解和你的贪心解在某一步不同交换这个不同点后最优解不会变差于是推出贪心解也能达到最优。第二种是数学归纳法——证明贪心选择后子问题依旧可以递归地贪心。第三种是剪枝法——说明选择贪心选项后一定存在一个包含该选项的最优解。我当年踩过一个经典坑活动选择问题。第一眼觉得很适合贪心按开始时间排序选最早开始的结果发现答案不对。正确做法是按结束时间排序每次都选结束时间最早的。这就是贪心策略没想清楚的典型。所以平时练题时每做一道贪心题都逼自己写出交换论证的三句话考试时才能熟练。2.3 图论高频模板Dijkstra、Prim/Kruskal、Floyd吉大第五道大题如果考图论最稳妥的做法是直接把模板背熟。Dijkstra堆优化版、Prim朴素版、Kruskal并查集版、Floyd三重循环这四套代码扎扎实实敲三遍以上考场上基本不会出错。先看最短路的经典模板typedef pairint, int PII; // {距离, 节点编号} void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); dist[s] 0; priority_queuePII, vectorPII, greaterPII pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; for (auto [v, w] : adj[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }这个模板有个细节用if (d dist[u]) continue做懒惰删除比维护visited数组更简洁而且不容易出错。错误在于忘记这个判断会导致同一个节点被多次松弛复杂度退化但结果正确如果加了dist[u]的更新却忘了push进队列结果就是错的。最小生成树里Kruskal比Prim更好写因为它只要把边按权排序然后并查集扫描。int find(int x) { return p[x] x ? x : p[x] find(p[x]); } void kruskal() { sort(edges.begin(), edges.end(), [](Edge a, Edge b){ return a.w b.w; }); int cnt 0, ans 0; for (auto e : edges) { int a find(e.u), b find(e.v); if (a ! b) { p[a] b; cnt; ans e.w; } } // cnt n-1 说明图不连通 }如果题目要求“先删去若干条边再在剩余图中求最小生成树”多半也是这个框架加一步预处理。这里要留意并查集初始化for (int i 1; i n; i) p[i] i这行写漏了find函数直接死循环。第二点如果图是稠密图m接近n²Prim朴素版O(n²)比Kruskal的O(mlogm)更优背模板时两个都准备着。第三点Floyd可以同时处理多源最短路和传递闭包如果问“哪些点对之间存在路径”用bitset优化传递闭包会快很多但这属于进阶内容基础好可以看看。2.4 字符串专题KMP与循环节问题字符串算法中KMP是第五道大题最喜欢考的。它的核心是next数组也叫部分匹配表。我的建议是每一次都手动模拟一遍构建next数组别只背代码否则换一个题目背景就转不过弯来。vectorint getNext(string p) { int m p.size(); vectorint nxt(m); int j 0; for (int i 1; i m; i) { while (j 0 p[i] ! p[j]) j nxt[j - 1]; if (p[i] p[j]) j; nxt[i] j; } return nxt; }注意这里是按“模式串下标从0开始”的写法很多教材用的是从1开始。考试前一定统一好自己习惯的下标风格别把两种混着写。KMP最常见的考点是求最小循环节一个字符串的最小循环节长度等于n - nxt[n-1]当n % (n - nxt[n-1]) 0时可以完全由循环节构成否则还是要补字符。这个结论在吉大往年真题里出现过一定要会推导。扩展KMPZ算法也会偶尔冒出来求每个后缀与某个前缀的最长公共前缀长度。如果题目出现“求字符串所有前缀的出现次数”这类问题Z算法一行代码的while循环配合差分数组复杂度O(n)就能搞定比用KMP每个前缀匹配一次优雅得多。2.5 二分答案把最优化问题转成判定问题二分答案的思路看似简单实际上很多人栽在“写出的判定函数是错的”上。它的适用范围是答案具有单调性——比如“如果x可行那么所有大于x的值或小于x的值也可行”。典型题型是最小化最大值、最大化最小值。我常用的二分答案模板bool check(int mid) { // 判断在某种贪心/模拟规则下能否让答案不超过/不小于mid return true/false; } int l 0, r 1e9, ans -1; while (l r) { int mid (l r) / 2; if (check(mid)) { ans mid; r mid - 1; } // 求最小可行值 else l mid 1; }这里最容易出错的是边界更新。如果check(mid)表示“mid可行”而你要找最小可行值那答案区间更新为r mid - 1如果找最大可行值就改成l mid 1。期中期末卷上我看到过不少同学把这两行写反导致最后答案错1。考试时先用小样例手推一遍边界才好。核心技巧check(mid)里通常要嵌套一个贪心或DP。比如经典题目“把数组分成k段使每段和的最大值最小”check函数里直接贪心扫描一遍数段数即可。二分答案考的不是二分本身而是你“从最优解问题转换为可行性问题”的建模能力。3. 综合真题拆解一道题走完从读题到AC的完整流程这一章我用一道综合性强、风格接近吉大第五道大题的原创题目把完整做题流程拆开讲。这种题的特点是一条题干里用多个知识点需要灵活串联。题目描述综合改编给定一张n个节点m条边的无向图每条边有长度w和修建费用c。现在要求从节点1到节点n的某条路径上每隔d距离就要设置一个补给站起点必须设置终点不一定必须设置如果终点前一个补给站到终点的距离小于d则终点可不设置。问你在所有可能的1到n路径中最小化“路径上补给站之间的最大间距”在此基础上再最小化总修建费用输出这两个值。拿到这道题先不要慌。我看到题面后大概三秒内就能确定算法框架因为题干里出现了两个明显信号一是“最小化最大值”这是二分答案的经典关键词二是在某个约束下去最小化费用说明第一个条件约束下还有第二层优化。完整思路如下3.1 第一步识别建模目标确定第一层算法题面问“最小化补给站之间的最大间距”这就是典型的最小化最大值问题。常规解法是二分这个最大间距Dcheck(D)要判断“是否存在一条路使得路上的相邻补给站间距不超过D”。怎么判断这里有一个转化原图的点可以分成两类一类是节点一类是补给站。但实际上补给站只能设置在节点上通常题面会隐含或直接说明那么我可以定义一个新图如果两个节点u和v之间在某条边上的距离不超过D并且沿着这个距离能走通那么就可以从u“跳”到v。更严谨地我把原图改造为以“一次补给能到达”作为边的图——新图中若原图上从u到v的最短路长度不超过D则新图连一条从u到v的边。那么问题变成新图中从1能否到达n这里就需要最短路算法先预处理任意两点间距离n在300以下可用Floyd O(n³)n在1000以上必须用n次Dijkstra O(n²logn)或多次BFS看数据范围灵活处理。3.2 第二步在边界条件下叠加费用最小化当二分找到最小可行间距D后第二问要求在间距不超过D的条件下使总修建费用最小。此时新图中每条从u到v的边其费用为“在原图最短路径上修建补给站边对应的最小修建费用”。这实际上是一个有边权的图上的最短路问题——用Dijkstra在新图上从1跑到n得到最短路径长度就是最小总费用。这时需要注意原来的二分check只需要判断连通性用的新图是无权图现在要最小化费用用的新图是有权图。两套新图结构一样只是边的权值不同。写代码时用一个函数统一构建新图参数是D返回一个邻接表check时用BFS求费用最小时用Dijkstra两个阶段都复用这个函数。3.3 第三步完整代码框架我用C把整道题的骨架写出来注释部分直接在代码里给出const int N 305; long long g[N][N], cost[N][N]; // 原图距离和费用 vectorpairint,long long newGraph[N]; // 新图邻接表 void buildNewGraph(int n, long long D) { for (int i 1; i n; i) newGraph[i].clear(); for (int i 1; i n; i) { for (int j 1; j n; j) { if (i ! j g[i][j] D g[i][j] INF) { newGraph[i].push_back({j, cost[i][j]}); // cost[i][j] 存的是在原图i到j最短路径上的最小修建费用 } } } } bool check(int n, long long D) { buildNewGraph(n, D); // BFS判断从1能否到达n vectorbool vis(n 1, false); queueint q; q.push(1); vis[1] true; while (!q.empty()) { int u q.front(); q.pop(); for (auto [v, w] : newGraph[u]) if (!vis[v]) { vis[v] true; q.push(v); } } return vis[n]; } long long dijkstra(int n) { vectorlong long dist(n 1, LLONG_MAX / 4); priority_queuepairlong long,int, vectorpairlong long,int, greater pq; dist[1] 0; pq.push({0, 1}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; for (auto [v, w] : newGraph[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } return dist[n]; }主函数里先做Floyd或多次Dijkstra预处理g和cost然后二分D找到最小可行间距后重新build新图跑Dijkstra输出结果。完整流程里最考验人的不是二分而是“把原题转换成新图”这一步——只要图建对了后面都是模板代码。3.4 原理解读为什么可以这么做这道题背后的逻辑是需求分两层第一层约束是所有补给站间距的上界第二层约束是费用。第一层约束天然满足二分答案的条件间距越大越容易连通所以二分一定能找到这个最小可行间距。第二层求的是满足该约束下的最小费用说明新图已经固定就是一个带权最短路问题。两个经典算法组合在一起就解决了这道题。这种“先转化图模型二分答案最短路”的组合拳在吉大第五道大题里出现过不止一次。把这道题的思路吃透考场上遇到背景换成什么网络路由、基因片段拼接本质上都不怕。4. 高频易错点与考场快速排查指南这一章全是实际考场上学生最容易踩的坑我按类型整理成速查表每一条都是从真实答题卡和复试机试的报错现场收集来的。4.1 易错点速查表错误类型现象原因解决方案数组越界运行时崩溃或答案错乱Floyd/Dijkstra数组开小了数组一律开N5循环时看清是n还是mDP初始化错误答案少1/多1dp[0]没设置成合法状态先把边界状态手算列出再写代码二分边界死循环程序跑不完/输出与预期不符l和r更新写反或mid计算溢出用l(r-l)/2并单独对mid做小样例验证最短路负权Dijkstra结果错图里有负边却用了Dijkstra有负边就用Bellman-Ford或SPFA并查集没初始化Kruskal结果错忘记写p[i]i每次测试用例开头做p数组初始化输出格式不符明明算对却给0分题目要求保留两位小数/输出换行交前5分钟仔细读输出要求4.2 考场上十分钟排查思路如果机试或笔试时发现自己代码过不了样例千万别慌。按照这个顺序排查第一步看数组大小和初始化位置80%的崩溃问题在这里第二步看二分或循环的边界条件拿纸笔手动跑一遍3个数据的样例第三步看状态转移是否把题目中的某个约束漏掉了比如“不能重复经过某个节点”“物品只能用一次”第四步确认不是类型溢出最短路和DP的INF要设成0x3f3f3f3f或LLONG_MAX/4不要用INT_MAX直接加。笔试场景手写代码和机试场景还不一样。笔试没法运行只能靠静态检查。我的习惯是写完代码后在草稿纸上画一个2~3条边的简单图或3~4个输入的小样例手工模拟一遍代码的每一行。模拟一遍能发现90%的逻辑漏洞如果手算和代码输出对上了基本上这道题的代码分就稳了。4.3 关于正确性的额外提醒第五道大题有些题目包含“证明题”性质的小问比如证明贪心策略正确、证明DP的无后效性、或者证明某种建图方式的等价性。这类问法看起来很吓人实际按套路写就能拿分。证明DP无后效性其实就是说明“当前状态一旦确定就不受后续状态影响”一般两句话带过。证明贪心正确就写交换论证的三句话。证明建图等价性就双向说明——原题的解能对应新图的解新图的解也能对应原题的解所以二者等价。这些证明的内容不需要天马行空格式整齐、逻辑链条完整即可。5. 备考冲刺建议与时间分配参考还有两周就考试或者还有一周就复试机试怎么安排复习性价比最高我根据自己当年的经验给出一个实操性很强的时间分配方案。5.1 分阶段复习路线第一阶段前5天集中过模板。每天敲两天经典算法模板Dijkstra、Kruskal、Prim、KMP、二分答案、区间DP、树形DP、背包DP。每个模板至少敲三遍每一遍都要完全闭卷。敲模板时不要直接复制以前写过的而是从空文件开始重新写直到不卡壳为止。第二阶段中间5天做真题和高质量模拟题。优先做吉大近五年的期末回忆题然后是其他学校同类课程的算法大题比如哈工大、北航、电子科大的算法设计与分析期末题。做综合大题时给自己掐时间一道题控制在40~50分钟模拟考场节奏。做完之后先别急着看答案把错误点记下来对照第4章的排查表总结自己的薄弱环节。第三阶段最后2~4天专项突破错题和背诵易错点。把第二阶段做错的题重新做一遍重点是搞明白为什么错而不是记住答案。同时把第4章的易错点表格过三遍考前当天早上再过一遍。5.2 各类题型的时间分配建议动态规划投入最多时间因为它是第五道大题的绝对主力。务必掌握区间DP、树形DP、背包DP、状态机DP四个方向。图论重点掌握最短路和最小生成树但不要忽略拓扑排序和强连通分量偶尔也会串进来。字符串KMP是核心Z算法看情况补充。贪心和二分答案属于“思路型”题目做题量决定了考场上能不能快速识别建议每种至少做15道题。5.3 心态与应试技巧最后说点务虚但很有用的东西。第五道大题不是每道题都需要全部解出来才拿满分。如果遇到一道特别难的题我的建议是先写出暴力解法或部分分的算法比如n≤20直接爆搜先把这部分分数拿到手然后再尝试优化。期末考试和考研复试都是按点给分你能写出状态转移方程但没写代码也有不少分空着就真的零分。拿到卷子后先花两分钟把五道题全部扫一遍。第五道大题如果一时没有思路先做前面几道题让大脑潜意识去处理。很多时候做完前面题再回头看建模思路自己就蹦出来了。这个现象不是我胡说而是大脑在后台进行模式匹配——你刷过的题型越多这个“灵感”来得越快。我个人备考时最喜欢的一句话是“算法题不是看会的是敲会的”。第五道大题更是如此光看答案觉得自己懂了合上资料自己写一遍才发现到处都是bug。把这篇文章里的模板敲熟、把真题过一遍、把易错点背牢你在考场上碰到第五道大题时看到的就是一道道似曾相识的朋友。