第一次考 PAT甲级 的时候我上来就栽了个跟头第二道 25 分的题卡了一个多小时第四道 30 分的大题连样例都没跑明白就交卷了。出了考场我复盘发现问题根本不在“会不会算法”而在“不知道甲级到底想要我输出什么”。后来我花了两周时间把近些年的题目按考点分类重刷每道题都补上“解析最优代码”才慢慢摸出这套考试的套路。这篇文章我就把这份整理过的题解合集展开讲清楚考什么、怎么分类、每类题的核心解法是什么、代码怎么写才稳以及我从真题里反推出来的避坑清单。不管你现在是刚接触 PAT 的小白还是刷过几十题但正确率上不去的选手按这个框架走效率都会比漫无目的地刷题高不少。1. 刷题之前先把甲级的“脾气”摸清楚我先说结论PAT甲级不是一个“比拼算法天赋”的考试更像一个“规定时间内稳定输出”的压力测试。它考的算法范围非常固定几乎不出偏题怪题但会在数据结构的组合、边界条件和输出格式上反复折磨人。1.1 考试的基本盘甲级是 PAT 计算机程序设计能力测试里的最高级别机考形式满分 100 分一般由 4 道题组成分值分布通常是 20 分、25 分、25 分、30 分考试时长在 150 分钟到 180 分钟之间浮动。重点在于它是按测试点给分的一道题哪怕只过了一部分测试点也能拿到对应比例的分而不是“要么满分要么零分”。这一点直接决定了应试策略——如果你在某一题上卡了 30 分钟还没思路果断放弃去做别的题往往比死磕到底更划算。1.2 核心考点其实就这些把真题过一遍之后你会发现高频考点高度集中在下面几块树的遍历与重构中序前序/后序重建二叉树、层序输出、BST 的插入与查找。图的遍历与连通性DFS/BFS 遍历、连通分量计数、去掉某个点后的连通分量变化。最短路问题Dijkstra 是绝对主角几乎必考而且普遍带“第二标尺”。并查集题型隐蔽经常包一层“社交网络”“聚类分组”的外壳。堆与完全二叉树判断大顶堆/小顶堆配合后序输出。排序与结构体处理多关键字排序、二分查找这类题不难但极其容易丢分。基本动态规划和字符串模拟背包、LIS、最长回文子串以及进制转换、日期处理等模拟题。我刚开始刷题时犯过一个错觉得“算法嘛会了模板就行”结果一上机就发现题目永远比你想象的绕一圈。它的难点不在于算法本身而在于“把实际问题转化成算法模型”的这一层抽象能力。1.3 近几年题目的“套壳”趋势要特别提醒的是甲级近几年越来越喜欢给算法穿上实际问题外衣。表面上是“城市救援队”“旅游规划”“社交平台好友分组”剥开来还是最短路、DFS、并查集。所以整理题解时不要太依赖“看题面猜算法”而是要做完题之后反推这道题考察的是哪个底层模型模型有没有变形这样刷才能对付五花八门的包装。2. 我整理这版“最优题解”时的分类框架这份合集的排序方式不是按题号而是按能力项分块。为什么这么分因为按题号刷会陷入“做一道忘一道”的困境按能力项刷才能真正建立解题直觉。2.1 分类优先级参考分类核心考点优先级说明树与二叉树遍历、重构、BST、堆必考花样最多分值占比最大图论与最短路Dijkstra、DFS/BFS、连通分量必考30分大题常驻选手并查集集合合并、连通分量、分组高经常藏在模拟题里排序与二分sort、cmp、lower_bound高简单但容易忽视细节字符串与模拟getline、进制、日期中高样例容易过边界容易炸动态规划背包、LIS、回文串中考得不深但必须会模板2.2 什么叫“最优”题解我知道“最优”这个词很容易引发争议所以先定义我自己的标准。一份题解配得上“最优”至少要满足三条复杂度不虚高。能用 O(n log n) 解决就不硬上 O(n²)但反过来也不要为了炫技引入线段树、平衡树这类重型结构。PAT 的数据范围决定了绝大多数题目用“复杂度正确、思路直接”的解法就能满分。代码可读性强变量名有意义核心步骤有注释。因为题解不只是给“已 AC”的人看的更是给“还不会”的人看的。边界处理稳。空树、单节点、最大值、最小值、输出末尾空格这些细节容易被忽略但恰恰是 PAT 扣分的高发区。我下面展开的每一道示例都会讲清楚“为什么这么选”“代码是怎么一步步写出来的”“最容易在哪翻车”而不是单纯丢一段能跑的代码。3. 树的遍历与重构一类题打穿所有变形树这块是甲级的“基本盘”尤其是一类经典题已知中序后序或前序重建二叉树并输出层序。我见过很多人看到“重建二叉树”就头皮发麻其实它的原理非常朴素——分治。3.1 核心原理中序序列是用来“切”左右子树的先回忆基本事实后序序列的最后一个元素一定是当前子树的根。在中序序列里根的左边是左子树右边是右子树。左子树有多少个节点在后序序列里就占据多少连续位置。所以只要拿到“根在中序中的下标”就能算出左子树的大小然后递归处理左右两半。这个过程可以用一句话概括用后序找根用中序分左右。我之所以推荐用“哈希表记录每个值在中序中的下标”是因为每次寻找根的位置都是 O(1)整体复杂度 O(n)。如果每次都用循环在中序里扫一遍复杂度会退化成 O(n log n) 甚至 O(n²)大数据点容易超时。3.2 完整代码中序后序重建并输出层序#include bits/stdc.h using namespace std; int n; vectorint in, post; unordered_mapint, int pos; // 值 - 中序下标 struct Node { int val; int l -1, r -1; }; vectorNode tree; int build(int inL, int inR, int postL, int postR) { if (inL inR || postL postR) return -1; int rootVal post[postR]; int idx pos[rootVal]; // 根在中序中的位置 int leftSize idx - inL; // 左子树节点数 int nodeId (int)tree.size(); tree.push_back({rootVal, -1, -1}); tree[nodeId].l build(inL, idx - 1, postL, postL leftSize - 1); tree[nodeId].r build(idx 1, inR, postL leftSize, postR - 1); return nodeId; } void levelOrder(int root) { queueint q; q.push(root); bool first true; while (!q.empty()) { int cur q.front(); q.pop(); if (!first) cout ; cout tree[cur].val; first false; if (tree[cur].l ! -1) q.push(tree[cur].l); if (tree[cur].r ! -1) q.push(tree[cur].r); } } int main() { cin n; in.resize(n); post.resize(n); for (int i 0; i n; i) cin post[i]; for (int i 0; i n; i) { cin in[i]; pos[in[i]] i; } int root build(0, n - 1, 0, n - 1); levelOrder(root); return 0; }3.3 最容易写错的三个点第一后序的左右子树边界。我见过无数人在这里纠结到下不去笔。记住两条公式左子树在后序中占据postL到postL leftSize - 1右子树在后序中占据postL leftSize到postR - 1第二递归终止条件。必须是inL inR || postL postR这种“区间为空”的判断而不是“区间长度等于 1 就返回”。否则单节点树会直接崩。第三层序输出末尾不能有多余空格。用first标志位控制这是 PAT 输出格式的通用套路。3.4 这个解法能扩展到哪些变形已知前序中序把post[postR]换成pre[preL]左子树边界公式对应调整即可。要求输出后序而不是层序把层序的队列改成递归的后序遍历。BST 的插入序列构建不需要中序直接按插入顺序建树然后判断某两个节点之间的关系这类题本质还是在考树的遍历。我在重刷这组题时明显感觉到树的遍历类题目只要把“数组模拟 递归分治 下标计算”这三件事练熟几乎所有变形都能在 15 分钟内拿下。而这三个技能本身也是后面堆、AVL、笛卡尔树等复杂结构的基础。4. 最短路第二标尺模板之外的决胜点甲级的最短路题几乎从不出“裸 Dijkstra”——它一定会给你加一个附加条件比如花费最少、时间最省、经过的点权最大、或者要求输出完整路径。我会把这一类统称为“最短路第二标尺”。4.1 为什么推荐 pre 数组 DFS 回溯而不是在 Dijkstra 里直接维护路径很多人一开始学 Dijkstra 时习惯在更新距离的同时直接记录一条路径比如path[v] u。这在“只有一条最短路径”时没问题但当存在多条等距路径、需要比较第二标尺时直接在 Dijkstra 里更新路径会非常容易漏情况你可能在某条等距路径出现时没有把前驱存下来到了第二标尺比较时就拿不到完整候选集。我的推荐做法是“两阶段分离”Dijkstra 阶段只负责计算最短距离并且把所有可能的前驱节点都存进pre[v]。DFS 阶段从终点往起点回溯生成每一条可能的路径顺带比较第二标尺。这样做最大的好处是Dijkstra 的逻辑始终只有“距离”一个维度简单不容易错第二标尺逻辑全部集中在 DFS 里以后题目换成“先比花费、再比节点数、再比字典序”只需要改 DFS 里一小段比较逻辑。4.2 完整代码最短路径条数 点权最大并输出路径下面这个例子是甲级里非常常见的一种组合每条边有长度每个点有“救援队数量”点权要求在所有最短路径里选择点权之和最大的一条并输出。#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; int n, m, s, d; vectorint weight; vectorvectorpairint, int g; // 邻接表: to, cost vectorvectorint pre; // 前驱集合 vectorint dijkstra(int src) { vectorint dist(n, INF); dist[src] 0; priority_queuepairint, int, vectorpairint, int, greater pq; pq.push({0, src}); while (!pq.empty()) { auto [du, u] pq.top(); pq.pop(); if (du ! dist[u]) continue; // 过期的堆元素 for (auto [v, w] : g[u]) { if (dist[v] du w) { dist[v] du w; pre[v].clear(); pre[v].push_back(u); pq.push({dist[v], v}); } else if (dist[v] du w) { pre[v].push_back(u); // 等距路径也要保存前驱 } } } return dist; } int maxWeight -1; int pathCount 0; vectorint bestPath, tmpPath; void dfs(int u, int src) { if (u src) { tmpPath.push_back(u); pathCount; int sum 0; for (int x : tmpPath) sum weight[x]; if (sum maxWeight) { maxWeight sum; bestPath tmpPath; } tmpPath.pop_back(); return; } tmpPath.push_back(u); for (int p : pre[u]) dfs(p, src); tmpPath.pop_back(); } int main() { cin n m s d; weight.resize(n); for (int i 0; i n; i) cin weight[i]; g.resize(n); pre.resize(n); for (int i 0; i m; i) { int u, v, w; cin u v w; g[u].push_back({v, w}); g[v].push_back({u, w}); } vectorint dist dijkstra(s); dfs(d, s); cout pathCount maxWeight \n; for (int i (int)bestPath.size() - 1; i 0; i--) { if (i ! (int)bestPath.size() - 1) cout ; cout bestPath[i]; } return 0; }4.3 这段代码里的几个细节必须说清楚if (du ! dist[u]) continue;这一段是“堆优化的灵魂”。优先队列里会存在旧数据如果du不等于当前dist[u]说明这个点已经通过更短路径更新过了当前这条是过期状态直接跳过。等距时用else if而不是if。因为dist[v] du w是在“更新失败”的前提下判断的如果用if且此时dist[v]刚被上一行更新为du w会把u重复加入pre[v]导致后面 DFS 出现重复路径。DFS 回溯时tmpPath里存的是从终点到起点的逆序所以最后输出bestPath时要倒序。这是 Dijkstra 路径回溯的固定姿势。4.4 如果第二标尺变成“费用最少”怎么办非常简单DFS 里不再统计点权和而是累加边权在边结构体里多存一个cost字段。DFS 回溯时维护costSum。比较逻辑改成if (costSum minCost)。如果你遇到“先比 A 再比 B”的复合标尺比如同样最短距离下先比费用、费用相同再比节点数那就把 DFS 的比较逻辑写成两个 if 嵌套即可。这就是两阶段分离的好处——Dijkstra 部分一行都不用改。5. 并查集、堆判定、STL 边界最容易白给的三个盲区先说一个我自己的观察甲级丢分最多的往往不是 30 分大题而是第二、第三道 25 分题。这些题算法模板并不难难在“变形”和“边界”。我挑了三个最典型的盲区展开。5.1 并查集模板要背到肌肉记忆变形要看清题意并查集的模板其实很短但每次考它都不会让你老老实实“合并两个集合”而是包装成各种问题社交网络每个人有几个爱好有相同爱好的人算一个圈子问有几个圈子、每个圈子多少人。判断连通分量给定无向图问整个图有多少个连通分量。删点模拟从图中去掉一个点后连通分量数怎么变。并查集的标准实现我直接放在这里vectorint fa, emp; void init(int n) { fa.resize(n 1); emp.resize(n 1, 0); for (int i 1; i n; i) fa[i] i; } int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); // 路径压缩 } void unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return; if (emp[ra] emp[rb]) swap(ra, rb); // 按秩合并 fa[rb] ra; if (emp[ra] emp[rb]) emp[ra]; }这里有两个实操建议路径压缩一定要写在find里否则大数据点的递归深度和查找效率都扛不住。合并之后统计集合数量不要去遍历每个节点的fa判断是否等于自己再计数因为经过路径压缩后fa不一定都指向根。正确做法是遍历每个节点用find(i)去碰撞或者维护一个count变量在unite里递减。至于“删掉一个点后有几个连通分量”这类题如果只问一次不要自己去实现高级动态图算法。最省事的方法就是先跑一次 DFS/并查集算原始连通分量数然后假设删掉某个点再对剩下节点跑一次 DFS。PAT 的数据范围下这么做完全能过而且不容易写错。5.2 堆的判断完全二叉树的层序天然就是数组存储甲级常考一道“给定完全二叉树的层序序列判断是大顶堆、小顶堆还是不是堆再输出后序遍历”。很多人在这一步会尝试建树其实完全没有必要。完全二叉树的层序序列本身就是它的数组存储结构根在下标 1节点i的左孩子是2*i右孩子是2*i1。判断逻辑极其简单从i1开始逐个访问左孩子2*i、右孩子2*i1如果存在。如果出现a[i] a[2*i]说明“父小于子”这种关系存在这能成为“小顶堆”的证据同时也是“大顶堆”的反例。如果出现a[i] a[2*i]同理成为“大顶堆”的证据、小顶堆的反例。只要同时出现过“父大于子”和“父小于子”就说明它不是堆。后序遍历同样用数组下标递归即可不需要建树void postOrder(int idx) { if (idx n) return; postOrder(idx * 2); postOrder(idx * 2 1); cout a[idx] (idx 1 ? \n : ); }这段代码的关键是递归出口idx n以及空格格式处理。我见过不少人在“每个测试点后换行”和“节点间空格”上踩坑这类细节其实比堆判断本身更值得留意。5.3 STL 与读入的边界条件最后说 STL 和输入输出的几个高频翻车点。cin 和getline混用这是甲级字符串题的重灾区。一旦你在cin n之后直接用getline(cin, str)第一行一定是空字符串因为cin 不会吃掉行尾的换行符。解决办法是在混用之前加一句cin.ignore()或者用getline先读掉那行残留。sort的比较函数必须是“严格弱序”a b返回 true相等时必须返回 false。写成return a b;在某些编译器下会 RE因为 sort 要求比较函数具备非自反性。unordered_map和map的选择PAT 老题用 map 写起来稳但查询 O(log n)如果 n 到 10^5 级别建议直接上unordered_map。不过注意unordered_map对键的哈希要求更高遇到结构体键需要自定义哈希函数否则编译报错。整数溢出涉及路径和、权值和、边权累加时如果累加量级可能超过 2^31直接用long long。PAT 的大多数题目 int 够用但养成“能 long long 就 long long”的习惯会省很多调试时间。6. 从真题里反推的避坑清单与冲刺节奏我每次考完或者帮别人看代码都会把问题归成表格里这几类。你可以把这个表当成提交前的自查清单。错误类型具体表现规避方法读题遗漏漏看输出格式里的换行/空格要求写 main 前先读“输出格式”全局变量脏数据多组数据时上次结果残留尽量用局部变量多组数据清空容器递归爆栈树退化成长链时递归层数过大改用迭代或确认环境栈大小getline 混用读不到期望字符串cin.ignore() 吃掉残留换行数组越界/死循环左右边界偏移计算错误打印区间 debug确认递归出口输出末尾空格部分系统严格比对输出用 first 标志位统一处理等距路径漏存前驱答案路径错误或偏少Dijkstra 中保留所有前驱再往后就是冲刺阶段的节奏安排。我的建议是三轮刷题法第一轮按能力项刷模板题。每做完一道题不要急着做下一道先把这道题的“题目模型”用一句话写下来比如“已知中序后序建树层序”“Dijkstra加第二标尺”。这些一句话笔记就是你后期复盘的索引。第二轮混合限时模拟。按正式考试的时间限制完整做一套真题中间不翻书、不查资料。模拟的核心目的不是“做对”而是训练“什么时候该放弃”。一道题卡 20 分钟没有完整思路果断跳下一道先把 20 分和 25 分的简单题拿稳。第三轮只刷错题。把前两轮错过的题重新归类找出错误集中在哪一类。比如我当年就是“树的下标边界”和“getline 读空行”反复错第二轮以后我每天先做两道树题热身再刻意练习字符串读入效果非常明显。另外提一句环境细节。如果你在 WSL 的 Ubuntu 里写 C建议把 VSCode 字体换成 Cascadia Code 或 JetBrains Mono 这类等宽字体比默认字体更贴近 macOS 下终端的效果看对齐关系时眼睛省力很多。本地编译时加上-stdc17 -O2 -Wall提前暴露警告信息提交到 OJ 后的行为也会更接近评测环境。最后再说一个我从真题里总结出来的观点甲级真正的难点从来不是“这个算法我不会”而是“我明明会这个算法为什么这道题没做出来”。绝大多数情况问题都出在第一步的模型抽象或者最后一步的边界检查。所以这份题解合集里我特意把每一道题的“模型抽象过程”写在解析的最前面代码只是结果。你能把题面翻译成模型代码就是水到渠成的事。希望这份整理能帮你少走我当初走过的那些弯路。 
长河君 · 2026/9/19 0:21:20 · 阅读 1.2k PAT甲级题解合集：从考点分类到最优代码的备考攻略
第一次考 PAT甲级 的时候我上来就栽了个跟头第二道 25 分的题卡了一个多小时第四道 30 分的大题连样例都没跑明白就交卷了。出了考场我复盘发现问题根本不在“会不会算法”而在“不知道甲级到底想要我输出什么”。后来我花了两周时间把近些年的题目按考点分类重刷每道题都补上“解析最优代码”才慢慢摸出这套考试的套路。这篇文章我就把这份整理过的题解合集展开讲清楚考什么、怎么分类、每类题的核心解法是什么、代码怎么写才稳以及我从真题里反推出来的避坑清单。不管你现在是刚接触 PAT 的小白还是刷过几十题但正确率上不去的选手按这个框架走效率都会比漫无目的地刷题高不少。1. 刷题之前先把甲级的“脾气”摸清楚我先说结论PAT甲级不是一个“比拼算法天赋”的考试更像一个“规定时间内稳定输出”的压力测试。它考的算法范围非常固定几乎不出偏题怪题但会在数据结构的组合、边界条件和输出格式上反复折磨人。1.1 考试的基本盘甲级是 PAT 计算机程序设计能力测试里的最高级别机考形式满分 100 分一般由 4 道题组成分值分布通常是 20 分、25 分、25 分、30 分考试时长在 150 分钟到 180 分钟之间浮动。重点在于它是按测试点给分的一道题哪怕只过了一部分测试点也能拿到对应比例的分而不是“要么满分要么零分”。这一点直接决定了应试策略——如果你在某一题上卡了 30 分钟还没思路果断放弃去做别的题往往比死磕到底更划算。1.2 核心考点其实就这些把真题过一遍之后你会发现高频考点高度集中在下面几块树的遍历与重构中序前序/后序重建二叉树、层序输出、BST 的插入与查找。图的遍历与连通性DFS/BFS 遍历、连通分量计数、去掉某个点后的连通分量变化。最短路问题Dijkstra 是绝对主角几乎必考而且普遍带“第二标尺”。并查集题型隐蔽经常包一层“社交网络”“聚类分组”的外壳。堆与完全二叉树判断大顶堆/小顶堆配合后序输出。排序与结构体处理多关键字排序、二分查找这类题不难但极其容易丢分。基本动态规划和字符串模拟背包、LIS、最长回文子串以及进制转换、日期处理等模拟题。我刚开始刷题时犯过一个错觉得“算法嘛会了模板就行”结果一上机就发现题目永远比你想象的绕一圈。它的难点不在于算法本身而在于“把实际问题转化成算法模型”的这一层抽象能力。1.3 近几年题目的“套壳”趋势要特别提醒的是甲级近几年越来越喜欢给算法穿上实际问题外衣。表面上是“城市救援队”“旅游规划”“社交平台好友分组”剥开来还是最短路、DFS、并查集。所以整理题解时不要太依赖“看题面猜算法”而是要做完题之后反推这道题考察的是哪个底层模型模型有没有变形这样刷才能对付五花八门的包装。2. 我整理这版“最优题解”时的分类框架这份合集的排序方式不是按题号而是按能力项分块。为什么这么分因为按题号刷会陷入“做一道忘一道”的困境按能力项刷才能真正建立解题直觉。2.1 分类优先级参考分类核心考点优先级说明树与二叉树遍历、重构、BST、堆必考花样最多分值占比最大图论与最短路Dijkstra、DFS/BFS、连通分量必考30分大题常驻选手并查集集合合并、连通分量、分组高经常藏在模拟题里排序与二分sort、cmp、lower_bound高简单但容易忽视细节字符串与模拟getline、进制、日期中高样例容易过边界容易炸动态规划背包、LIS、回文串中考得不深但必须会模板2.2 什么叫“最优”题解我知道“最优”这个词很容易引发争议所以先定义我自己的标准。一份题解配得上“最优”至少要满足三条复杂度不虚高。能用 O(n log n) 解决就不硬上 O(n²)但反过来也不要为了炫技引入线段树、平衡树这类重型结构。PAT 的数据范围决定了绝大多数题目用“复杂度正确、思路直接”的解法就能满分。代码可读性强变量名有意义核心步骤有注释。因为题解不只是给“已 AC”的人看的更是给“还不会”的人看的。边界处理稳。空树、单节点、最大值、最小值、输出末尾空格这些细节容易被忽略但恰恰是 PAT 扣分的高发区。我下面展开的每一道示例都会讲清楚“为什么这么选”“代码是怎么一步步写出来的”“最容易在哪翻车”而不是单纯丢一段能跑的代码。3. 树的遍历与重构一类题打穿所有变形树这块是甲级的“基本盘”尤其是一类经典题已知中序后序或前序重建二叉树并输出层序。我见过很多人看到“重建二叉树”就头皮发麻其实它的原理非常朴素——分治。3.1 核心原理中序序列是用来“切”左右子树的先回忆基本事实后序序列的最后一个元素一定是当前子树的根。在中序序列里根的左边是左子树右边是右子树。左子树有多少个节点在后序序列里就占据多少连续位置。所以只要拿到“根在中序中的下标”就能算出左子树的大小然后递归处理左右两半。这个过程可以用一句话概括用后序找根用中序分左右。我之所以推荐用“哈希表记录每个值在中序中的下标”是因为每次寻找根的位置都是 O(1)整体复杂度 O(n)。如果每次都用循环在中序里扫一遍复杂度会退化成 O(n log n) 甚至 O(n²)大数据点容易超时。3.2 完整代码中序后序重建并输出层序#include bits/stdc.h using namespace std; int n; vectorint in, post; unordered_mapint, int pos; // 值 - 中序下标 struct Node { int val; int l -1, r -1; }; vectorNode tree; int build(int inL, int inR, int postL, int postR) { if (inL inR || postL postR) return -1; int rootVal post[postR]; int idx pos[rootVal]; // 根在中序中的位置 int leftSize idx - inL; // 左子树节点数 int nodeId (int)tree.size(); tree.push_back({rootVal, -1, -1}); tree[nodeId].l build(inL, idx - 1, postL, postL leftSize - 1); tree[nodeId].r build(idx 1, inR, postL leftSize, postR - 1); return nodeId; } void levelOrder(int root) { queueint q; q.push(root); bool first true; while (!q.empty()) { int cur q.front(); q.pop(); if (!first) cout ; cout tree[cur].val; first false; if (tree[cur].l ! -1) q.push(tree[cur].l); if (tree[cur].r ! -1) q.push(tree[cur].r); } } int main() { cin n; in.resize(n); post.resize(n); for (int i 0; i n; i) cin post[i]; for (int i 0; i n; i) { cin in[i]; pos[in[i]] i; } int root build(0, n - 1, 0, n - 1); levelOrder(root); return 0; }3.3 最容易写错的三个点第一后序的左右子树边界。我见过无数人在这里纠结到下不去笔。记住两条公式左子树在后序中占据postL到postL leftSize - 1右子树在后序中占据postL leftSize到postR - 1第二递归终止条件。必须是inL inR || postL postR这种“区间为空”的判断而不是“区间长度等于 1 就返回”。否则单节点树会直接崩。第三层序输出末尾不能有多余空格。用first标志位控制这是 PAT 输出格式的通用套路。3.4 这个解法能扩展到哪些变形已知前序中序把post[postR]换成pre[preL]左子树边界公式对应调整即可。要求输出后序而不是层序把层序的队列改成递归的后序遍历。BST 的插入序列构建不需要中序直接按插入顺序建树然后判断某两个节点之间的关系这类题本质还是在考树的遍历。我在重刷这组题时明显感觉到树的遍历类题目只要把“数组模拟 递归分治 下标计算”这三件事练熟几乎所有变形都能在 15 分钟内拿下。而这三个技能本身也是后面堆、AVL、笛卡尔树等复杂结构的基础。4. 最短路第二标尺模板之外的决胜点甲级的最短路题几乎从不出“裸 Dijkstra”——它一定会给你加一个附加条件比如花费最少、时间最省、经过的点权最大、或者要求输出完整路径。我会把这一类统称为“最短路第二标尺”。4.1 为什么推荐 pre 数组 DFS 回溯而不是在 Dijkstra 里直接维护路径很多人一开始学 Dijkstra 时习惯在更新距离的同时直接记录一条路径比如path[v] u。这在“只有一条最短路径”时没问题但当存在多条等距路径、需要比较第二标尺时直接在 Dijkstra 里更新路径会非常容易漏情况你可能在某条等距路径出现时没有把前驱存下来到了第二标尺比较时就拿不到完整候选集。我的推荐做法是“两阶段分离”Dijkstra 阶段只负责计算最短距离并且把所有可能的前驱节点都存进pre[v]。DFS 阶段从终点往起点回溯生成每一条可能的路径顺带比较第二标尺。这样做最大的好处是Dijkstra 的逻辑始终只有“距离”一个维度简单不容易错第二标尺逻辑全部集中在 DFS 里以后题目换成“先比花费、再比节点数、再比字典序”只需要改 DFS 里一小段比较逻辑。4.2 完整代码最短路径条数 点权最大并输出路径下面这个例子是甲级里非常常见的一种组合每条边有长度每个点有“救援队数量”点权要求在所有最短路径里选择点权之和最大的一条并输出。#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; int n, m, s, d; vectorint weight; vectorvectorpairint, int g; // 邻接表: to, cost vectorvectorint pre; // 前驱集合 vectorint dijkstra(int src) { vectorint dist(n, INF); dist[src] 0; priority_queuepairint, int, vectorpairint, int, greater pq; pq.push({0, src}); while (!pq.empty()) { auto [du, u] pq.top(); pq.pop(); if (du ! dist[u]) continue; // 过期的堆元素 for (auto [v, w] : g[u]) { if (dist[v] du w) { dist[v] du w; pre[v].clear(); pre[v].push_back(u); pq.push({dist[v], v}); } else if (dist[v] du w) { pre[v].push_back(u); // 等距路径也要保存前驱 } } } return dist; } int maxWeight -1; int pathCount 0; vectorint bestPath, tmpPath; void dfs(int u, int src) { if (u src) { tmpPath.push_back(u); pathCount; int sum 0; for (int x : tmpPath) sum weight[x]; if (sum maxWeight) { maxWeight sum; bestPath tmpPath; } tmpPath.pop_back(); return; } tmpPath.push_back(u); for (int p : pre[u]) dfs(p, src); tmpPath.pop_back(); } int main() { cin n m s d; weight.resize(n); for (int i 0; i n; i) cin weight[i]; g.resize(n); pre.resize(n); for (int i 0; i m; i) { int u, v, w; cin u v w; g[u].push_back({v, w}); g[v].push_back({u, w}); } vectorint dist dijkstra(s); dfs(d, s); cout pathCount maxWeight \n; for (int i (int)bestPath.size() - 1; i 0; i--) { if (i ! (int)bestPath.size() - 1) cout ; cout bestPath[i]; } return 0; }4.3 这段代码里的几个细节必须说清楚if (du ! dist[u]) continue;这一段是“堆优化的灵魂”。优先队列里会存在旧数据如果du不等于当前dist[u]说明这个点已经通过更短路径更新过了当前这条是过期状态直接跳过。等距时用else if而不是if。因为dist[v] du w是在“更新失败”的前提下判断的如果用if且此时dist[v]刚被上一行更新为du w会把u重复加入pre[v]导致后面 DFS 出现重复路径。DFS 回溯时tmpPath里存的是从终点到起点的逆序所以最后输出bestPath时要倒序。这是 Dijkstra 路径回溯的固定姿势。4.4 如果第二标尺变成“费用最少”怎么办非常简单DFS 里不再统计点权和而是累加边权在边结构体里多存一个cost字段。DFS 回溯时维护costSum。比较逻辑改成if (costSum minCost)。如果你遇到“先比 A 再比 B”的复合标尺比如同样最短距离下先比费用、费用相同再比节点数那就把 DFS 的比较逻辑写成两个 if 嵌套即可。这就是两阶段分离的好处——Dijkstra 部分一行都不用改。5. 并查集、堆判定、STL 边界最容易白给的三个盲区先说一个我自己的观察甲级丢分最多的往往不是 30 分大题而是第二、第三道 25 分题。这些题算法模板并不难难在“变形”和“边界”。我挑了三个最典型的盲区展开。5.1 并查集模板要背到肌肉记忆变形要看清题意并查集的模板其实很短但每次考它都不会让你老老实实“合并两个集合”而是包装成各种问题社交网络每个人有几个爱好有相同爱好的人算一个圈子问有几个圈子、每个圈子多少人。判断连通分量给定无向图问整个图有多少个连通分量。删点模拟从图中去掉一个点后连通分量数怎么变。并查集的标准实现我直接放在这里vectorint fa, emp; void init(int n) { fa.resize(n 1); emp.resize(n 1, 0); for (int i 1; i n; i) fa[i] i; } int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); // 路径压缩 } void unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return; if (emp[ra] emp[rb]) swap(ra, rb); // 按秩合并 fa[rb] ra; if (emp[ra] emp[rb]) emp[ra]; }这里有两个实操建议路径压缩一定要写在find里否则大数据点的递归深度和查找效率都扛不住。合并之后统计集合数量不要去遍历每个节点的fa判断是否等于自己再计数因为经过路径压缩后fa不一定都指向根。正确做法是遍历每个节点用find(i)去碰撞或者维护一个count变量在unite里递减。至于“删掉一个点后有几个连通分量”这类题如果只问一次不要自己去实现高级动态图算法。最省事的方法就是先跑一次 DFS/并查集算原始连通分量数然后假设删掉某个点再对剩下节点跑一次 DFS。PAT 的数据范围下这么做完全能过而且不容易写错。5.2 堆的判断完全二叉树的层序天然就是数组存储甲级常考一道“给定完全二叉树的层序序列判断是大顶堆、小顶堆还是不是堆再输出后序遍历”。很多人在这一步会尝试建树其实完全没有必要。完全二叉树的层序序列本身就是它的数组存储结构根在下标 1节点i的左孩子是2*i右孩子是2*i1。判断逻辑极其简单从i1开始逐个访问左孩子2*i、右孩子2*i1如果存在。如果出现a[i] a[2*i]说明“父小于子”这种关系存在这能成为“小顶堆”的证据同时也是“大顶堆”的反例。如果出现a[i] a[2*i]同理成为“大顶堆”的证据、小顶堆的反例。只要同时出现过“父大于子”和“父小于子”就说明它不是堆。后序遍历同样用数组下标递归即可不需要建树void postOrder(int idx) { if (idx n) return; postOrder(idx * 2); postOrder(idx * 2 1); cout a[idx] (idx 1 ? \n : ); }这段代码的关键是递归出口idx n以及空格格式处理。我见过不少人在“每个测试点后换行”和“节点间空格”上踩坑这类细节其实比堆判断本身更值得留意。5.3 STL 与读入的边界条件最后说 STL 和输入输出的几个高频翻车点。cin 和getline混用这是甲级字符串题的重灾区。一旦你在cin n之后直接用getline(cin, str)第一行一定是空字符串因为cin 不会吃掉行尾的换行符。解决办法是在混用之前加一句cin.ignore()或者用getline先读掉那行残留。sort的比较函数必须是“严格弱序”a b返回 true相等时必须返回 false。写成return a b;在某些编译器下会 RE因为 sort 要求比较函数具备非自反性。unordered_map和map的选择PAT 老题用 map 写起来稳但查询 O(log n)如果 n 到 10^5 级别建议直接上unordered_map。不过注意unordered_map对键的哈希要求更高遇到结构体键需要自定义哈希函数否则编译报错。整数溢出涉及路径和、权值和、边权累加时如果累加量级可能超过 2^31直接用long long。PAT 的大多数题目 int 够用但养成“能 long long 就 long long”的习惯会省很多调试时间。6. 从真题里反推的避坑清单与冲刺节奏我每次考完或者帮别人看代码都会把问题归成表格里这几类。你可以把这个表当成提交前的自查清单。错误类型具体表现规避方法读题遗漏漏看输出格式里的换行/空格要求写 main 前先读“输出格式”全局变量脏数据多组数据时上次结果残留尽量用局部变量多组数据清空容器递归爆栈树退化成长链时递归层数过大改用迭代或确认环境栈大小getline 混用读不到期望字符串cin.ignore() 吃掉残留换行数组越界/死循环左右边界偏移计算错误打印区间 debug确认递归出口输出末尾空格部分系统严格比对输出用 first 标志位统一处理等距路径漏存前驱答案路径错误或偏少Dijkstra 中保留所有前驱再往后就是冲刺阶段的节奏安排。我的建议是三轮刷题法第一轮按能力项刷模板题。每做完一道题不要急着做下一道先把这道题的“题目模型”用一句话写下来比如“已知中序后序建树层序”“Dijkstra加第二标尺”。这些一句话笔记就是你后期复盘的索引。第二轮混合限时模拟。按正式考试的时间限制完整做一套真题中间不翻书、不查资料。模拟的核心目的不是“做对”而是训练“什么时候该放弃”。一道题卡 20 分钟没有完整思路果断跳下一道先把 20 分和 25 分的简单题拿稳。第三轮只刷错题。把前两轮错过的题重新归类找出错误集中在哪一类。比如我当年就是“树的下标边界”和“getline 读空行”反复错第二轮以后我每天先做两道树题热身再刻意练习字符串读入效果非常明显。另外提一句环境细节。如果你在 WSL 的 Ubuntu 里写 C建议把 VSCode 字体换成 Cascadia Code 或 JetBrains Mono 这类等宽字体比默认字体更贴近 macOS 下终端的效果看对齐关系时眼睛省力很多。本地编译时加上-stdc17 -O2 -Wall提前暴露警告信息提交到 OJ 后的行为也会更接近评测环境。最后再说一个我从真题里总结出来的观点甲级真正的难点从来不是“这个算法我不会”而是“我明明会这个算法为什么这道题没做出来”。绝大多数情况问题都出在第一步的模型抽象或者最后一步的边界检查。所以这份题解合集里我特意把每一道题的“模型抽象过程”写在解析的最前面代码只是结果。你能把题面翻译成模型代码就是水到渠成的事。希望这份整理能帮你少走我当初走过的那些弯路。