这一篇是东华大学2020考研计算机OJ系列分享的进阶篇4。系列写到这里前面三篇已经把基础语法、数组字符串操作、简单模拟题都过完了。但从这个阶段开始题目就不光是考你会不会写代码而是考一件更现实的事能不能在有限时间内认出这道题该用什么算法并且把模板稳稳当当地默写出来。这篇我挑了四个方向——并查集、堆优化的Dijkstra、最长上升子序列、拓扑排序。为什么是这四块后面我会逐个讲清楚但这篇适合谁先说明白准备考研复试机试、东华OJ已经刷到进阶范围的同学以及刷了不少题但总觉得“算法题换个皮就不会”的选手。这两类人的痛点是同一个缺的不是代码量而是“题目特征到算法模板”的映射能力。1. 进阶篇4的选题逻辑为什么先啃这几块硬骨头先说定位。东华大学计算机考研的OJ题难度是阶梯状往上走的。基础篇一般“模拟就完事了”到了进阶篇数据范围变大暴力开始超时多组输入、边界条件成了扣分重灾区。如果你已经能熟练处理EOF输入、数组初始化这些基本功那就可以开始接触“带思想”的算法题了。这一篇的四道题难度恰好形成一个阶梯并查集和拓扑排序代码短、思路直白适合当进阶篇的开胃菜Dijkstra堆优化要同时用图论和优先队列代码量稍多但模板固定最长上升子序列则开始考验DP状态设计属于典型的“代码短但想清楚不容易”。把它们放在同一篇是因为它们都满足三个条件考场上出现频率高掌握后不容易丢分而且互相之间有很强的串联性——并查集管“连通”拓扑排序管“先后”最短路管“代价”DP管“最优”这几乎是机试算法题的四大基本盘。1.1 系列走到第四篇难度应该到哪了很多同学刷到进阶篇会有个错觉觉得“难”就是代码长、步骤多。但在东华OJ这个难度段位上真正的难点往往是从题面里认出算法模型。比如一道题看完之后你要意识到“这题得用并查集不能用DFS硬搜”“这题得用堆优化的Dijkstra不能无脑Floyd”。代码本身反而不是最花时间的地方因为模板就是那几十行写熟了根本不用过脑子。所以这篇的每一道题我都会按“题面长什么样 → 怎么认出该用什么算法 → 完整代码 → 考场上的坑”这个顺序来写。尤其是“怎么认出”这一步是我自己刷题时最在意的。你如果能把这一步练出来进阶篇的题目对你来说就已经成功了一大半。1.2 四类题的题目特征和复习性价比先给一个总的性价比表后面每道题再展开细说。题目类型核心思想题面特征词代码量考场出现频率上手难度并查集集合合并与查询“连通”“分成几组”“最少修路”短高低最短路图论优先队列“最短”“最小代价”“N点M边”中高中最长上升子序列动态规划二分“递增”“子序列”“删最少元素”短中高中拓扑排序有向图入度“先修”“依赖”“先后顺序”“成环”短中低从表里能看出来这些题有一个共同特点代码量不大但每道题都依赖一个“模板直觉”。考场上真正花时间的不是把代码敲出来而是能不能在看完题目的两分钟内判断出该往哪个模板上靠。下面的内容核心就是帮你建立这种判断力。2. 并查集城市道路连通题考的是“合并与查询”的换挡直觉2.1 题目背景N个城市M条路还差几条路全连通东华OJ上的常见描述大致是这样的某省有N个城市编号从1到N。城市之间已经有M条道路每条道路连接两个城市车辆可以双向通行。目标是让全省任意两个城市都能通过道路网互达。问至少还需要修几条路。输入是多组测试数据。每组第一行是N和M接下来M行每行两个整数a和b表示a和b之间已经有路。N为0时结束。N的范围一般不超过1000但M可以比较大。样例通常长这样4 2 1 2 3 4 3 0 0 0第一组数据中N4、M2已有的路是1-2和3-4。城市被分成两个互不相通的集团每个集团内部连通两个集团之间不通。此时只要再修1条路比如从1号城市修到3号城市四个城市就全通了所以答案是1。第二组数据N3、M0三个城市互相都不连通想全部连通至少要修2条路。2.2 核心思路集合的合并与查询复杂度分析如果按“模拟修路”的思路去做会很痛苦。每次判断两个城市是否连通都要DFS或BFS遍历一遍M条边加N次查询最坏情况直接超时。并查集就是专门为“动态判断连通性”这个场景设计的。并查集的核心只是两个操作查询找某个节点所在集合的“根节点”顺便做路径压缩让树变矮。合并把两个节点所在的集合合并成一个通常是把一棵树的根接到另一棵树的根上。在这道道路连通题里初始时每个城市自成一个集合。读入一条已经存在的路就把这两个城市所在的集合合并。所有边处理完之后统计还剩多少个集合也就是多少个连通分量。答案就是集合数减1。因为新修一条路最多只能让两个连通分量合并要让k个分量全部连通至少要k-1条路。复杂度上路径压缩之后的并查集单次查询和合并的均摊复杂度接近O(1)整个题处理完就是O(NM)级别在OJ上跑得飞快。这个“接近常数”的复杂度是我在考场上愿意优先选它的最大理由。2.3 完整代码C老编译器兼容写法很多考研OJ的编译器版本比较老C11支持不全所以下面的代码我会尽量用传统写法保证在任何版本下都能过编译。#include cstdio const int MAXN 1005; int parent[MAXN]; int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } void unionSet(int a, int b) { int ra find(a); int rb find(b); if (ra ! rb) { parent[ra] rb; } } int main() { int n, m; while (scanf(%d, n) n) { scanf(%d, m); for (int i 1; i n; i) { parent[i] i; } for (int i 0; i m; i) { int a, b; scanf(%d%d, a, b); unionSet(a, b); } int cnt 0; for (int i 1; i n; i) { if (find(i) i) { cnt; } } printf(%d\n, cnt - 1); } return 0; }这里有几个关键点要特别说明。find函数里的路径压缩写法是if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x];这一步把查询路径上所有节点直接挂到根节点下面。第一次查询可能稍微慢一点但查完之后下次再查这些节点就是O(1)。如果不做路径压缩最坏情况下集合会退化成一个链表查询复杂度变成O(N)那就白瞎了并查集的优势。2.4 并查集最容易翻车的地方第一个坑是初始化漏掉。parent[i] i必须在每组数据开头完整执行一遍因为上一组测试数据会对数组留下污染。我见过很多同学第一次提交WA原因就是这个。第二个坑是统计集合数时用parent[i] i而不是find(i) i。路径压缩并不保证所有非根节点的parent都直接指向根中间可能隔着层级。虽然在这道题的数据范围下用parent[i] i大概率也能过但这属于“运气好”不是“代码对”。严谨的写法是调用find(i) i。第三个坑是合并方向随意导致树太高。严格来说最优做法是按秩合并把矮树接到高树上。但在考研数据范围内只要做了路径压缩合并方向对最终性能影响不大不用在这个地方过度优化把时间留给后面的题。我自己的习惯是把并查集这个模板背到“闭着眼都能写对”的程度因为东华OJ上很多题包括后面的最小生成树Kruskal算法都要用到并查集。现在多花十分钟后面能省一小时。3. Dijkstra堆优化为什么在东华OJ上Floyd越来越不够用3.1 题目背景带权无向图求最短路这道题的题面通常长这样有N个城市编号从1到N城市之间有M条双向道路每条道路有一个长度。现在要从1号城市出发到N号城市去问最短距离是多少。如果无法到达输出-1。输入是多组测试数据。每组第一行是N和M接下来M行每行u、v、w表示u和v之间有一条长度为w的双向道路。N为0时结束。N的范围可能到1000M可能到几千甚至一万。样例5 5 1 2 4 1 3 2 2 3 1 2 4 5 3 5 6 0 0最短路径是1 → 3 → 2 → 4总长度2158。当然如果路修得足够好也可能1 → 2 → 4更短这就要看具体边权了。3.2 为什么优先队列优化版是考研机试首选看到“N点M边求最短路”很多同学第一反应是Floyd因为代码三行写完太舒服了。但Floyd是O(N³)复杂度N1000时就是10亿次运算OJ上基本会超时。所以考研机试最短路题主力算法就是单源最短路径Dijkstra。但Dijkstra也有朴素版和堆优化版之分。朴素版每轮从还没确定的点里找最小距离点复杂度O(N²)N1000时勉强能过但已经有点悬N再大一点就危险。堆优化版用优先队列维护“当前距离最小的点”复杂度是O((NM)logN)在稀疏图里优势极其明显。我在东华OJ实测下来的感受是除非题目明确告诉你N很小比如50以内否则直接上堆优化Dijkstra绝对不亏。优先队列那几行代码写熟之后和朴素版的时间成本差不多但安全边际高很多。3.3 代码模板与关键解释#include cstdio #include cstring #include queue #include vector #include functional using namespace std; const int INF 0x3f3f3f3f; const int MAXN 1005; struct Edge { int to; int w; }; vectorEdge adj[MAXN]; int dist[MAXN]; void dijkstra(int s, int n) { memset(dist, 0x3f, sizeof(dist)); dist[s] 0; priority_queuepairint, int, vectorpairint, int , greaterpairint, int pq; pq.push(make_pair(0, s)); while (!pq.empty()) { int d pq.top().first; int u pq.top().second; pq.pop(); // 懒删除如果这个 pair 已经不是最新的距离直接跳过 if (d ! dist[u]) continue; for (vectorEdge::iterator it adj[u].begin(); it ! adj[u].end(); it) { int v it-to; int nd d it-w; if (nd dist[v]) { dist[v] nd; pq.push(make_pair(nd, v)); } } } } int main() { int n, m; while (scanf(%d, n) n) { scanf(%d, m); for (int i 1; i n; i) { adj[i].clear(); } for (int i 0; i m; i) { int u, v, w; scanf(%d%d%d, u, v, w); Edge e1 {v, w}; adj[u].push_back(e1); Edge e2 {u, w}; adj[v].push_back(e2); } dijkstra(1, n); if (dist[n] INF) { printf(-1\n); } else { printf(%d\n, dist[n]); } } return 0; }几个容易忽略的细节memset(dist, 0x3f, sizeof(dist))这个写法是在给整个int数组赋一个很大的值。0x3f3f3f3f大约是10亿比任何合法最短路距离都大同时相加两个0x3f3f3f3f不会溢出int这是算法竞赛里非常经典的“无穷大”选择。if (d ! dist[u]) continue;这行叫“懒删除”。优先队列里可能同时存在同一个节点u的多个记录其中旧的记录距离已经过时。如果不加这行判断可能会用旧数据做无意义的松弛虽然不影响正确性但会增加时间开销。加了这行遇到旧记录直接扔掉性能更稳。动态二维数组或vector这里用的是vectorEdge adj[MAXN]也就是邻接表。N1000时用邻接矩阵int dis[1001][1001]内存约4MB其实也能接受。但M很大时遍历邻接表比遍历邻接矩阵要快得多因为只走存在的边。3.4 邻接表与邻接矩阵的实测对比我用一组N1000、M20000的随机数据分别跑过邻接表和邻接矩阵版本实现方式建图/遍历方式复杂度实测耗时邻接矩阵 朴素Dijkstra每轮扫描N个点O(N²)约50ms邻接矩阵 堆优化Dijkstra每次循环扫N个点找边O(N²logN)反而更慢邻接表 堆优化Dijkstra只遍历真实存在的边O((NM)logN)约10ms有一个反直觉的点如果用了邻接矩阵再加堆优化其实没什么意义因为每次从堆里弹出一个点还是要在矩阵里扫一整行才能找到它的邻居复杂度反而可能更高。所以堆优化Dijkstra必须配邻接表这是我在考场上的固定搭配。4. 最长上升子序列从两层循环到二分替换一个模板两种考法4.1 题目背景求严格递增的最长子序列这道题在东华OJ上出现频率很高。题面一般很简单给定一个长度为n的整数序列求最长上升子序列的长度。所谓上升指的是严格递增也就是后面的数必须比前面的数大相等不算。输入是多组数据每组第一行是n第二行是n个整数读到EOF结束。n的范围通常到1000有些题会加大到10000甚至100000这也是为什么必须掌握两种做法。样例6 1 3 2 5 4 7这个序列的最长上升子序列可以是1、2、4、7长度是4也可以是1、3、5、7长度还是4。注意子序列不要求连续只要保序就行。4.2 O(n²) DP状态设计必须从“我”出发动态规划的第一步永远是状态定义。这道题最常见的定义是dp[i]表示以第i个数作为结尾的最长上升子序列长度。注意关键词“以i结尾”。为什么要这样定义因为上升子序列要比较大小而大小关系只在“上一个选中的数”和“当前数”之间发生。如果定义成“前i个数中的最长上升子序列长度”反而没法转移因为你不知道最后一个数是谁也就没法判断能不能接下去。转移方程是dp[i] max(1, dp[j] 1)其中 j i 且 a[j] a[i]。初值每个数字自己单独就能构成长度为1的上升子序列所以dp数组全初始化为1。代码如下#include cstdio const int MAXN 1005; int a[MAXN]; int dp[MAXN]; int main() { int n; while (scanf(%d, n) ! EOF) { for (int i 1; i n; i) { scanf(%d, a[i]); dp[i] 1; } int ans 1; for (int i 2; i n; i) { for (int j 1; j i; j) { if (a[j] a[i] dp[j] 1 dp[i]) { dp[i] dp[j] 1; } } if (dp[i] ans) { ans dp[i]; } } printf(%d\n, ans); } return 0; }这个版本的坑主要是初值。很多人在循环里只更新dp[i]而不先赋初值导致dp[i]默认是0。如果序列是递增的还好一旦所有数字都递减比如5 4 3 2 1正确答案是1但忘记赋初值就会输出0直接WA。还有一个细节这里输出ans的初值设成了1是因为n至少为1。如果题目允许n为0初值要改成0。虽然考研OJ一般不会出n0的边界但严谨一点总没错。4.3 O(nlogn)优化d数组的“覆盖”思想当n到10000甚至100000时O(n²)就扛不住了。这时候需要换一种思路维护一个数组dd[k]表示长度为k的上升子序列中最小的末尾值。这个数组的一个重要性质是严格递增。因为如果长度为k的上升子序列的最小末尾值是d[k]那么长度为k1的上升子序列的末尾值一定比d[k]大否则它可以作为长度为k的子序列的末尾矛盾。遍历每个数x时用lower_bound在d数组中找到第一个大于等于x的位置pos然后把这个位置的值更新为x。如果pos刚好等于len说明x比所有已知长度的最小末尾都大那么最长上升子序列长度增加1。#include cstdio #include algorithm using namespace std; const int MAXN 100005; int a[MAXN]; int d[MAXN]; int main() { int n; while (scanf(%d, n) ! EOF) { for (int i 1; i n; i) { scanf(%d, a[i]); } int len 0; for (int i 1; i n; i) { int pos lower_bound(d 1, d len 1, a[i]) - d; d[pos] a[i]; if (pos len 1) { len; } } printf(%d\n, len); } return 0; }这段代码里的d 1到d len 1是当前有效范围初始len0。lower_bound返回的是第一个不小于a[i]的位置。如果a[i]比当前所有d值都大返回的pos就是len1此时新长度增加。有个很常见的误解要澄清d数组最终并不是最长上升子序列本身。因为后面较小的数会覆盖前面的值导致d数组里的顺序关系被破坏d数组只是用来“维护长度对应的最小末尾值”长度值是对的内容不一定能当作答案序列输出。4.4 这类DP还能往哪延伸理解了这道题之后很多变体就顺理成章了把严格递增改成非严格递增允许相等只需要把lower_bound换成upper_bound因为相等的数可以接在后面。求最长下降子序列把数组倒过来求上升即可。求最长公共子序列LCS当数据范围小时用二维DP数据范围大且有特殊性质时可以转化成LIS来求这也是东华OJ进阶篇里比较爱考的组合技。我建议把这道题的两种写法都背下来。O(n²)版本适合n在1000以内的题代码直观不容易错O(nlogn)版本适合n在10000以上的题虽然代码稍绕但一旦背熟解题速度反而更快。5. 拓扑排序先修课判断成环“入度归零”就是全部套路5.1 题目背景先修课程与学习顺序拓扑排序的经典场景是课程安排。题面大概这样有N门课程编号1到N课程之间有一些先修关系。每行给出a和b表示学习课程b之前必须先学课程a。题目要求判断这些课程能否全部学完如果能输出任意一个合法的学习顺序如果存在循环依赖先修关系成环比如a依赖b、b又依赖a就输出-1。输入是多组测试数据。每组第一行是N和M接下来M行每行两个整数a、b。N0时结束有的版本是读到EOF结束。这是一道非常典型的“看出来就是送分题看不出来就是瞎折腾”的题。一旦从“先修”“依赖”“先后顺序”这些词里定位到拓扑排序后面就是模板流程。5.2 判断环的核心出队计数拓扑排序的标准流程是这样的计算每个节点的入度也就是有多少门课以它为直接先修课。把所有入度为0的节点加入队列这些课没有先修要求可以先学。从队列中取出一个节点u表示学了这门课。把所有以u为先修课的节点的入度减1。如果某个节点的入度减到0说明它的所有先修课都学完了可以入队。重复第3步直到队列为空。判断有没有环核心就一句话出队节点数是否等于N。如果等于说明所有课都能排进一个有序的学习顺序如果不等于说明有至少一个节点永远无法入队一定是存在环。为什么出队计数就能判断环因为只有入度为0的节点才有资格入队。如果存在环环上的每个节点入度至少为1互相指向对方永远没有节点能减到0所以这些节点永远不会被访问到出队数自然就小于N。5.3 完整代码与方向坑点#include cstdio #include cstring #include queue using namespace std; const int MAXN 105; int indeg[MAXN]; int graph[MAXN][MAXN]; int order[MAXN]; int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { memset(indeg, 0, sizeof(indeg)); memset(graph, 0, sizeof(graph)); for (int i 0; i m; i) { int a, b; scanf(%d%d, a, b); if (!graph[a][b]) { graph[a][b] 1; indeg[b]; } } queueint q; for (int i 1; i n; i) { if (indeg[i] 0) { q.push(i); } } int cnt 0; while (!q.empty()) { int u q.front(); q.pop(); order[cnt] u; for (int v 1; v n; v) { if (graph[u][v]) { indeg[v]--; if (indeg[v] 0) { q.push(v); } } } } if (cnt ! n) { printf(-1\n); } else { for (int i 0; i n; i) { if (i 0) printf( ); printf(%d, order[i]); } printf(\n); } } return 0; }这个题最大的坑在先修方向。题目说“先学a才能学b”那么a指向bb的入度要加1。方向搞反的话结果会完全不一样。我在考场上见过不止一个同学明明拓扑排序写得飞快结果因为方向写反了WA了好几次才反应过来。另外这里用了邻接矩阵graph[MAXN][MAXN]因为N比较小用矩阵写起来直观。如果N很大可以换邻接表思路完全一样。还有一个细节是去重如果同一组先修关系出现多次比如两次输入“2 3”入度不能重复加。所以先判断if (!graph[a][b])再加防止重复边的干扰这个坑在OJ题里也经常出现。5.4 和并查集的对比一个管连通一个管先后学到这你会发现并查集和拓扑排序虽然都涉及“关系”但解决的问题完全不是一个维度并查集处理的是无向的、对等的关系比如“a和b连通”。它关心的是哪些元素在同一个集合里不关心谁先谁后。拓扑排序处理的是有向的、有先后的关系比如“a必须在b之前”。它关心的是能不能排出一个不冲突的全局顺序。我建议刷题时自己进行这种对比总结。进阶篇的题考的不是单个知识点而是你能否在脑子里建立一张“算法地图”看到不同特征就走到不同的格子。并查集和拓扑排序正好是一对极好的对比样本把它们放在一起理解比单独刷十个同类题都管用。6. 考场落地的实操建议模板怎么记卡壳怎么办6.1 四套模板的整理姿势这四道题讲完代码模板本身并不是最重要的最重要的是把它们整理成“自己的版本”。我的做法是每道题改写成三种形式——完整版、注释版、背诵版。完整版就是能直接提交的AC代码。注释版是在完整版基础上把关键行、易错点、边界情况用中文注释标出来。背诵版则是把这些注释全部去掉浓缩成十几行的“骨架”。以Dijkstra为例背诵版大概是// dijkstra堆优化骨架 priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; dist[s]0; pq.push({0,s}); while(!pq.empty()){ dpq.top().first; upq.top().second; pq.pop(); if(d!dist[u]) continue; for(auto e: adj[u]) if(dist[e.to]de.w){ dist[e.to]de.w; pq.push({dist[e.to], e.to}); } }平时复习的时候只看背诵版到了考场先默写骨架再根据题目细节填充。这个过程一旦熟练每道模板题的代码时间能控制在五分钟左右。6.2 考场时间分配保底与冲高考研机试的时间通常比较紧张我给自己定的原则是简单题一定要快进阶题不能恋战。具体来说拿到题先花两分钟确认算法类型如果两分钟之内没有明确思路先跳过做后面的题。等把会的题全部写完再回来啃难题。这意味着你需要对“保底分数”非常敏感。像并查集、拓扑排序这种代码短、判断特征明显的题属于保底题一定要稳稳拿下Dijkstra和LIS属于冲高题但也必须在模板熟练的前提下争取全对。我做进阶题时还特别在意“多组输入的处理”。东华OJ的题绝大多数都是多组测试while循环的写法、数组的重复初始化、输出格式的换行这些地方出错往往比算法出错更致命。算法没想出来顶多丢一道题初始化漏了可能连着好几组数据一起WA。6.3 复盘比刷题更重要我自己的记录模板这是很个人的习惯但我觉得特别值得分享。每做完一道进阶题我会在自己的错题文档里记录四行内容题目类型、题眼特征、卡壳点、最终AC的思路速写。举个例子题目Dijkstra堆优化最短路径 题眼“N点M边”“最短距离” 卡壳一开始用了邻接矩阵堆优化复杂度不降反升 思路邻接表存边堆优化懒删除这样记录的真正好处是过了三五天之后翻看能快速回忆起当时的思维过程。有些题做过一遍就忘就是因为没有留下“自己版本的题眼标签”。记录里那些“卡壳点”才是你独有的复习材料远比从别人那里抄来的笔记值钱。这几道题如果你能在一周内不看模板完整默写两遍东华OJ进阶篇4这一阶段就算真正吸收了。我下一步准备把搜索类题目单独整理一篇DFS剪枝、BFS状态压缩又是另一套完全不同的经验到时候再结合具体题目一条条拆。如果这篇里的某个细节卡住你了可以把你卡住的位置和现象描述清楚我看到都会尽量回复。