折腾了一个多月的PAT甲级刷题记录目前推进到1159正在二刷补代码。这个系列不是标准答案汇总也不是什么高分速成攻略而是把每道题从“看到题面”到“AC通过”中间那段思考过程、测试点踩坑记录和参考代码完整沉淀下来。很多同学后台问我说网上题解一大把为什么还要自己整理。道理很简单题解只告诉你“怎么写”但这个系列想告诉你“为什么这么写”“测试点为什么这么设”“报错之后往哪改”。这个系列主要解决三个问题第一按题型把PAT甲级1001-1159的核心思路串起来让你拿到题能快速定位到对应的数据结构和算法第二逐题分析测试点告诉你每个测试点可能埋了什么陷阱而不是等提交挂了再盲猜第三二刷过程中把代码陆续补上形成“思路-测试点-提示-代码”四段式笔记。适合正在备考PAT的考生、准备机试和保研面试的同学也适合想用真题提升算法落地能力的开发者。1. 先看清PAT甲级到底在考什么1.1 甲级考纲结构与常驻题型PAT甲级的难度曲线不是线性上升的1001到1120左右有一个明显的“刷题舒适区”过了1130以后综合题比例变高一道题往往要同时用上两三种算法。从整体看高频考点集中在几个方向字符串处理与格式化输出、基础模拟、树的遍历与重建、图的最短路径与连通性、排序与二分查找、并查集与最小生成树、少量动态规划。这跟考研机试、面试手撕算法题的侧重点高度重合。把考纲结构记在脑子里很重要。你刷题的时候不用纠结“这题是哪里的真题”只需要判断“它考的是树还是图、是模拟还是DP”就能快速定位到对应的解题模板。这也是我整个系列拆分题目的核心依据。很多时候卡题不是因为算法不会而是你根本没意识到这道题属于哪个类型。1.2 为什么思路和测试点分析比刷题数量更重要我见过刷了三百多道题的人遇到新的树重建题照样卡壳也见过只刷一百五十道但每道都吃透拿满分的。差距就在“有没有把题吃透”。吃透的标准不是AC而是三点能讲清楚为什么用这个数据结构、能说出测试点考察了哪类边界情况、能在不参考题解的情况下独立复现代码。这个系列每一题都按这个标准来整理。测试点分析尤其容易被忽视。很多人以为测试点就是随机生成的数据其实不是。每个测试点往往是出题人针对某个特殊情况专门构造的用例。比如字符串题里可能有一个测试点专门考察空串或全零树题里可能有一个测试点专门考察单节点图论题里可能有一个测试点专门考察多条最短路径的选择规则。你只有把这些测试点的逻辑拆出来才能在下次遇到同类题时条件反射地提前规避。1.3 刷题前需要备好的基本功清单在动手刷题之前有几个基本功必须过关否则写代码会非常痛苦。我整理了一张自查表模块具体内容检查标准C/C基础指针、引用、结构体、动态内存能独立实现链表和二叉树STL容器vector/map/set/queue/stack/priority_queue/unordered_map清楚每个容器的底层结构和常用接口的时间复杂度算法模板DFS/BFS、Dijkstra、Kruskal、Prim、二分、并查集、排序能在10分钟内在纸上默写核心框架输入输出scanf/printf、getline、cin优化了解不同读入方式的效率差异数学基础素数判断、最大公约数、进制转换常见数学题不会卡住我建议用两周时间专门补这些知识不要边刷边查。尤其是STL的时间复杂度比如map底层是红黑树插入和查找都是O(logn)unordered_map是哈希表平均O(1)。很多超时问题就出在选错了容器这种错误可以通过基本功排查直接避免。1.4 从1001到1159的整体节奏安排我的实际刷题节奏分三轮。第一轮按题号顺序刷从1001推到1159目标是所有题目见一面能AC的尽量AC卡住超过两小时的标记出来。第二轮按专题刷把树、图、字符串、模拟分成几大类集中用两周时间攻克薄弱环节。第三轮就是现在这个二刷阶段不看题解独立把重点题的代码重新写一遍同时整理成系列内容。第一轮最容易犯的错误是“刷到哪算哪”没有计划的随缘刷题。我给自己的规则是每天固定三道雷打不动。状态好的时候多做状态不好也要至少做一道保持手感。千万别小看这个习惯手感这种东西断了之后重新捡起来很费劲连续刷题才能保持对题型的敏感度。2. 高频题型的解题思路与测试点拆解2.1 字符串处理与模拟细心就是核心竞争力字符串题在1001-1159区间内出现频率很高包括大数格式化、多项式加法、回文判断、数字转英文等经典题。这类题的技术含量集中在两点输入格式解析和输出格式控制。算法层面几乎不设门槛真正拉分的是边界情况想得全不全。以1001 AB Format为例核心思路是把整数转成字符串后从右往左每三位加一个逗号同时要处理负数、零、位数不足三种情况。它的测试点设计很有代表性有一个测试点是普通的小数加法有一个是负数情况还有一个是结果接近int上限的大数。很多人在这题拿“格式错误”本质原因是把逗号插在负号后面或者没考虑位数恰好是3的倍数时不加逗号的边界。这类题的通用排查顺序是先验证样例再补充“00”“负数大数”这类特殊组合最后用最大边界数据检查溢出。有人会觉得这种题没技术含量但考试时这类题恰恰是送分题拿下它你才有底气去啃后面的图论和树。提示字符串模拟题提交前养成顺手测试“单字符输入”“空行输入”“全零输入”的习惯能避免一大半格式错误。2.2 树的遍历与重建递归边界就是命门树相关的题目在整个甲级里占了很大比重比如中序后序重建二叉树、层序遍历统计叶子节点、二叉搜索树的插入与遍历等。树的题一旦AC挂了大部分是栽在递归边界上而不是栽在建树逻辑上。拿中序后序重建二叉树举例核心思路是后序序列的最后一个节点是根用中序序列把左右子树分开然后递归重建。看似简单的分治逻辑测试点却喜欢考查三种情况只有一个节点时递归能否正确终止所有节点都偏向一侧时索引计算会不会越界节点值不是从0开始连续时用数组还是map来定位根节点。我的经验是树的题目一定要在纸上画几棵特殊形态的树再写代码空树、单节点树、链状树、满二叉树。这四个形态能覆盖绝大多数测试点。我还习惯在递归函数入口打印一下当前的左右子树范围排查索引越界时特别有用。二刷时树的题建议全部手写一遍递归和非递归两种版本因为非递归版本在链状树的情况下能有效规避栈溢出。2.3 图论与最短路径Dijkstra与DFS的组合拳图论题在甲级里是拉开差距的分水岭。Emergency城市救援、Public Bike Management公共自行车、Travel Plan旅行计划等都是经典题核心都是最短路径问题。难度不在Dijkstra本身而在于“第二标尺”的处理路径条数、最大物资、最少费用、最少步数全都是套路。Dijkstra加第二标尺的通用写法是在更新最短距离时如果发现更短的路径则重置标尺数组如果路径长度相等则按第二标尺规则更新。测试点特别喜欢造“多条最短路径”的数据考察你是否正确处理了并列情况。另一个高频坑是起点和终点相同的情况有些考生在初始化时没把起点标记为已访问导致结果差了一个初始值。处理这类题我建议先写Dijkstra跑通样例再单独构造一个“多条最短路径”的测试数据验证第二标尺逻辑。如果不确定用记忆化深搜可以保住部分分数但效率不高只建议作为考场保底策略。实际写多了你会发现Dijkstra的模板就这么几行真正决定成败的是初始化是否完整、比较逻辑是否严格符合题目规则。2.4 排序、并查集与二分模板熟了能救命排序相关题目常以“自定义排序规则”出现比如按总分、平均分、ID进行排名。这块容易错的不是排序算法本身而是排序规则的边界。比如“分数相同则并列排名但下一名次被占”这个规则第一次写很容易出错。用结构体配合sort时自定义比较器一定要满足严格弱序否则在数据量大时可能触发未定义行为导致边界数据莫名报错。并查集的题目如求删除某个节点后的连通分量个数看起来是图论本质是并查集维护连通性。删掉一个节点后计算剩余连通分量核心操作是遍历所有边合并两端点跳过被删除的节点。测试点常考查删除多个不同节点的场景每次都需要重建并查集这时要注意时间复杂度。优化思路是预先存好所有边每个查询重新初始化并查集数组即可。二分查找在Radix这类进制题中体现得最明显。你不仅要把进制转换函数写对还要意识到进制的最大值不是36而是可能达到超长整数范围。这种题必须用二分来确定进制测试点会专门用最大值边界和非法输入来卡你。遇到“寻找最小满足条件的值”这类描述第一反应就应该是二分答案这是PAT里非常高频的套路。2.5 综合应用与动态规划能拿一档是一档甲级里的动态规划题占比不大但几乎都是压轴题。常见的是最大子段和问题核心是维护当前子段和与全局最大子段和。这道题的测试点坑特别典型全为负数时按题意要求输出首尾元素并附上0很多人忘记处理“最大子段和等于0”的边界情况导致最后一个测试点过不去。面对DP类题目我一般先看能不能转换成一维DP或区间DP不能的话果断放弃满分用小规模暴力捞分。备考阶段最重要的是把经典DP模型背包、LIS、LCS练熟万一遇到变体也能快速套模板。甲级DP题的核心特征很明显求最值、求数量、求是否可行看到这三个关键词中的任何一个都要往DP方向上想一想。3. 拿到一道甲级题后我的完整解题流程3.1 第一步把样例和题目背景彻底吃透很多人拿到题直接看输入输出格式然后开写这是最浪费时间的做法。我会先读完整题目背景把题目里涉及的数据结构、操作规则、特殊约定圈出来。然后盯着样例动手推算每一行输入对应什么结构输出结果的每个字符是怎么得出的。推样例的过程就是跟出题人对齐认知的过程。以银行排队模拟题为例样例里每个客户的服务时间、窗口数量、关门时间之间的关系你不亲手推一遍很难理解“顾客在17:00前到达但服务可能持续到关门后”的设定。很多考生在这个题上卡住不是算法不会而是没搞清楚“过了17:00还未开始的顾客不计入统计”这个规则。3.2 第二步确定数据结构与算法模板推完样例马上问自己三个问题数据是什么形态——树、图还是线性序列有没有明显的“最短/最大/计数/存在性”关键词内存和时间限制大概多少这三个问题定下来数据结构和算法也八成就定了。比如题目中出现“路径”“距离”“救援队数量”优先考虑图论和Dijkstra出现“层序”“叶子节点”就往二叉树靠出现“排名”“分数”“序列”多半是排序加自定义比较。我习惯在本地维护一个模板文件夹把Dijkstra、DFS、BFS、并查集、Kruskal的模板各自存好需要时复制改参数比每次从零手写快很多。不过提醒一句模板一定要自己敲过几遍最好能默写否则考场紧张时根本想不起来。3.3 第三步先写主流程再补边界条件我的代码习惯是先把主流程完整写出来哪怕边界还没想清楚也要先跑通普通数据。主流程指从读入数据到输出结果的核心逻辑链。写完之后再逐一补边界输入数据可能为空吗节点编号从0开始还是从1开始负数怎么处理输出有没有首尾空格要求边界条件不要靠猜而是从测试点分析反推。很多测试点的存在就是为了打破你的默认假设比如你以为节点编号一定小于100实际上可以是int上限附近的值。这种时候数组开多大、用不用map就是生死线。另外我习惯把所有的数组和vector大小都写成“范围5”宁可多开一点也不要越界这个习惯帮我躲过了无数次段错误。3.4 第四步提交后的反馈循环提交之后不要只看分数一定要看是哪个测试点挂了。若报“答案错误”立刻回到代码里检查对应的分支逻辑若报“段错误”优先看数组下标和递归深度若报“运行超时”检查是否能用哈希缓存结果或换更快的算法。我自己最受用的一个习惯是把每个测试点的失败截图存下来二刷时这些截图就是最精准的复习资料比任何错题本都好用。4. 常见报错信息与测试点排查技巧实录4.1 格式错误的幕后推手格式错误在PAT判分里非常严格常见于输出结果本身正确但多了或少了空格、换行、逗号。比如遍历输出一个序列时很多人习惯“每个元素后跟一个空格”结果最后一个元素也带上了空格直接格式错误。我的解决套路是用“当前索引是否为第一个”来控制分隔符这样比“是不是最后一个”写起来更不容易错。另一个容易踩的坑是输出空行输入数据为0时有些题要求输出空行有些题要求什么都不输出必须逐题读清楚规则不要自己想当然。4.2 运行超时与死循环的排查顺序PAT甲级的运行超时很常见原因大概分三类算法复杂度太高比如可以用哈希处理的查找用了O(n)遍历输入输出太慢cin没关同步导致大规模数据读入超时死循环或特殊数据下无法正常终止。排查看三类检查循环里的while条件是否可能永远为真特别是处理数字位数时容易死循环把cin改为scanf或加上ios::sync_with_stdio(false)用unordered_map替代map做一个性能测试。如果还是超时基本可以确认算法本身复杂度不行需要换思路而不是继续堆补丁。注意PAT的输入规模往往不写在前言里而是藏在测试点权重中。点开某个超时测试点看到分值较大基本可以判断数据规模不小直接按最大复杂度反推算法是否可行。4.3 段错误的高频来源段错误最常见的来源是数组越界和递归栈过深。树的递归遍历在链状树情况下很容易栈溢出这时要么改成非递归的栈模拟要么减少递归层数。还有一种隐蔽的越界建图用二维数组顶点编号从1开始如果忘了留出下标0的位置就会在输入阶段悄悄越界直到最后才爆出段错误。我排查段错误的顺序是先检查所有数组和vector的size是否比数据范围大1再检查递归函数的退出条件最后用调试器定位崩溃位置。大多数段错误都逃不过这顺序。还有一点使用vector时用at()访问代替下标访问可以在开发阶段快速暴露越界位置虽然提交时建议换回[]因为at有性能开销。4.4 部分测试点不通过的五个排查方向单独某些测试点不过说明代码处理了大部分情况但特定情况没照顾到。我一般的排查顺序检查特殊边界空输入、最小输入、最大输入、重复值、逆序、全相同。检查数据类型范围int换成long long试试有些题答案会超出int范围。检查索引偏移从0开始还是1开始、有没有越界访问。检查排序比较器是否满足严格弱序map的key比较是否有遗漏。检查初始化全局变量和数组是否需要清零上一次循环的脏数据是不是还留在里面。这个清单我打印出来贴在显示器边上卡题的时候按顺序过一遍大部分问题能在十分钟内定位。4.5 一个很容易被忽略的“答案错误”来源很多时候答案错误不是算法问题而是输出精度或格式问题尤其是浮点数题目。甲级题目有时候要求保留1位小数有时候要求保留2位写printf的时候格式串错了很难发现。我的经验是浮点数一律用printf(%.1f)这类显式控制不要用cout的默认精度。还有一类是取整规则比如“四舍五入”还是“向上取整”还是“向下取整”题目文字里通常会有明确描述。我遇到过不少考生因为默认四舍五入结果题目要求截断好几个测试点全挂。这类问题在提交前一定要回到原题确认而不是靠经验猜测。5. 二刷阶段的执行方案与更新规划5.1 为什么一刷完必须二刷一刷的本质是“看懂答案”二刷的本质是“默写答案”。很多题一刷AC后过两周再写会发现记忆模糊这不是记忆力问题而是大脑还没有把解题逻辑内化。二刷是唯一能确认内化程度的手段。我二刷时不会翻开一刷代码而是只看题目描述在空白编辑器里从零写起。遇到卡壳就翻一刷笔记但只允许看思路部分不允许看代码。这样能最大程度激活自己的设计能力而不是依赖复制粘贴。很多题我第一次AC用了半天二刷只花二十分钟那种“脑子里的路径通了”的感觉才说明真正掌握了。5.2 二刷的优先级安排二刷不必从头到尾重新做我按四个优先级来安排第一优先是之前卡了很久的题也就是耗时超过两小时的那批第二优先是高频经典题比如树的重建、Dijkstra、并查集类第三优先是一刷AC很快但综合度高的题因为这类题往往隐藏测试点多值得重新写一遍验证第四优先才是顺序扫尾把剩下没复习到的题过一遍。二刷过程中我会顺手把参考代码补充到这个系列里目前的节奏是每补完一组就发布一组采用“思路-测试点分析-提示-代码”四段式结构。代码都经过本地编译和样例验证个别题目我会标注多种解法方便读者根据自己的水平选择。5.3 系列内容后续怎么扩展目前覆盖的是1001到1159这个区间基本含盖了PAT甲级的高频题型。后续更新按题号顺序推进同时把一刷过程的错题集整理到每个章节末尾方便按专题快速回看。如果读者有特别想看的题目也可以在评论区告诉我我会优先分析大家卡得最多的题。内容形式方面我在考虑给每道高频题补一个“复杂度分析”小节明确说清楚时间复杂度为什么是这个量级、空间占用到什么程度。这样不仅对考试有帮助对面试中系统设计的前置分析也有参考价值。毕竟刷题最终不只是为了那一个分数算法素养的提升才是更长期的收益。6. 写在最后的一些实在话说实话刷PAT甲级这事情天赋的作用远远小于方法和坚持。我自己在1001到1159这条路上交了不少学费最大的体会是“思路和测试点分析比代码本身值钱”。代码网上到处都是但为什么那样写、测试点为什么那样设、遇到报错该往哪个方向查这些才是真正拉开差距的东西。这个系列会保持更新二刷的代码也在陆续补齐。如果你正在刷题建议不要贪快把每一道题当成一个小项目去研究。卡住两个小时不可怕可怕的是卡了五分钟就去看答案看完觉得自己会了合上页面又是一片空白。跟着思路分析走一遍再对照测试点分析检查自己漏了哪类边界最后独立把代码写出来这套流程走下来一道题顶得上别人囫囵刷十道。