2019年冬季我报名了PAT甲级考试。那天下午三点交卷走出机房的时候手还在抖不是冷是代码写到后半段脑子有点缺氧。三个月前我还对PAT一无所知三个月后我坐在考场上用C写完最后一题这中间踩的坑、绕的路、总结出来的经验值得原原本本写下来。我写这篇东西不是想复述某某真题的标准答案而是想聊聊这场考试的体感、难度分布、我丢分的地方以及从考后复盘倒推出来的那条备考路线。不管你是正在准备PAT的在校生还是想通过PAT给自己的简历加点分的工作党这篇应该都不会白看。1. 我为什么会在冬天报名PAT甲级动机、门槛和回报1.1 甲级的定位不是门槛是一块有分量的敲门砖先把这个考试说清楚。PATProgramming Ability Test是某高校计算机相关院系主办的一项程序设计能力测试分乙级、甲级、顶级三个档。甲级面向有数据结构基础的人群考察范围主要是数据结构、算法设计、C/C和部分STL应用满分100时间180分钟题量是四道大题。它和竞赛的区别在于竞赛讲究在最短时间内解最难的题而PAT更看重稳定地、准确地解决实际场景下的算法问题。换句话说竞赛是冲刺跑PAT是匀速长跑带障碍。我当时报名的原因很现实某高校的夏令营筛选简历时会直接看PAT成绩或者类似的算法认证一些公司的开发岗校招笔试也会给持有高分的候选人免掉机试环节。与其在简历上写熟悉常用算法这种空话不如拿一张可量化的成绩单。甲级80分以上在简历上写出来人工筛选简历的时候面试官至少能确认你具备基本的数据结构和算法能力沟通成本明显降低。1.2 冬季场的时间点对考研人和求职人意味着什么PAT每年有固定日期就近安排考场冬季场通常安排在12月初前后。这个时间点很微妙考研的人刚进入政治和英语的冲刺阶段校招的人则处在秋招尾巴和春招备战的空窗期。我身边不少同学把冬季场当作考研复习的中场调剂也有人把它当作春招简历的加分材料。我自己的状态是本科课程刚结束专业课阶段算法课上过一遍但动手写题的积累几乎为零。距离冬季场大约三个月我给自己定了一个目标冲80分。因为甲级80分以上在多数筛选场景下才算有效分数。从后来的复盘看三个月时间每天保证1到2小时的高质量刷题是完全够用的。前提是别假装努力别只刷会做的题。2. 2019年冬季场四道题描出的能力轮廓2.1 四题分别考了什么一个整体的题型快照考场上拿到试卷我先把四道题全部翻了一遍。下面这段题的回忆可能有细节偏差但考察方向我记得很清楚供参考。第一题通常是最基本的数据结构模拟考点集中在字符串处理、排序、查找类似把一组记录按规则排序并格式化输出。这类题看着简单却最容易在边界条件上翻车。第二题是图论具体是判断图的性质需要堆栈或集合配合深度优先遍历。第三题是一棵二叉树的遍历与重建输入是中序和前序要求输出层序或者判断是否为某类特殊树。第四题是综合题常见套路是带限制的最短路变体需要在基础算法之上加入业务逻辑约束。这个分布和我考前预判的基本一致前三题与其说是考会不会某个高级算法不如说是在考能不能把基础数据结构用对。真正拉分的地方集中在第四题和第三题的边界条件。2.2 第二题的坑图和Union-Find的边界第二题我印象最深因为它看起来像并查集实际上不是。题目给出一组边要求统计在无向图中有多少个独立的连通分量每个分量还需要满足某种度数的约束条件。我第一反应是用并查集写完一跑样例全对。但随后我注意到题面里的一个关键信息边是单向读入的而查询的关系要求双向成立。这意味着不能用简单的并查集合并需要把邻接表建出来之后单独做遍历。我当时的处理方式是退回用邻接表加DFS在每次DFS前用一个集合记录访问过的节点边界条件是节点编号范围比较大不能用固定数组标记只能顺手用了unordered_set。现在回头看这道题想考察的是对图模型的理解是否到位给一个看似并查集的壳实际考的是遍历和连通分量计数。如果只背了并查集模板做到一半会非常难受。2.3 压轴题的复杂度预判别被长题面吓住第四题拿到手第一眼我有点慌题面接近一页半描述了一个路径选择的场景要求输出某种情况下的最小开销。这种题其实是纸老虎。把自然语言翻译成图论模型之后它就是一个典型的最短路变体只是在最短路的代价之外额外加了一个资源消耗维度要求在选择路径时不能超过某个资源上限。我的做法是直接改写成二维的状态节点状态是(节点编号, 已消耗资源)边上转移时检查资源是否超限最后用优先队列跑一遍类似Dijkstra的逻辑。这样做的复杂度是O(E * R)的级别题面给了资源上限1000节点数500边的数量在可接受范围内完全能在时限内跑完。这一题给我的教训是压轴题的价值不在于算法有多新奇而在于你能不能冷静地把长题面脱水成模型。读不懂题再熟Dijkstra也白搭。3. 我在考场丢分最多的三种情况复盘完整排查链经历一次真实考场比刷十套模拟卷更能暴露问题。这里我把自己丢过分、甚至险些丢分的三种情况完整复现一遍排查过程供还没上过考场的读者作为前车之鉴。3.1 建图时把有向图当无向图样例却全对情况出现在第二题。我在读题时看到一个词“相邻”下意识认为关系是双向的于是建的是无向图然后跑DFS样例输出和预期一致。但我没有仔细看题面中关于“查询方向”的附加说明。直到我检查数据范围时翻开草稿纸重新读了一遍原题描述才注意到输入的关系是有方向的图本身是无向的但查询需要检查对某个方向的处理。这类错误最坑的地方在于样例的构造往往非常温和用双向关系去跑也能通过。真正的检查方法是做一次思维实验如果A能走到B那么B是否能按照同样的规则走到A如果不能就必须给每条边标方向或者在合并时做特殊判断。我在考场上意识到这一点之后把邻接表的push_back改成了按方向插入然后把DFS的进入条件补了一个方向的判定才稳住这道题。这里给所有备考者的建议是读题时遇到关系类描述第一件事是圈出“双向”“单向”“互相”“依次”这些词并在草稿纸上画一个小的样例图自测一下反向是否存在。样例全过不代表你的模型对只能说明你通过了出题人给的靶子。3.2 明明数据量不大程序却Stack Overflow第三题要求重建二叉树并做某些遍历。我第一版用了递归建树加递归层序遍历写完自测小数据正常。但构造一个极端链状树之后直接栈溢出。当时第一反应是编译器栈空间太小后来冷静排查才发现问题在递归深度。这里普及一个经验OJ或者考试环境的默认栈空间一般都不大递归深度超过一万就可能爆栈而二叉树在最坏情况下退化成链表深度等于节点数很容易到一万以上。我当时的解法是把建树的递归保留但把遍历部分改成非递归用栈模拟操作这样至少把树的遍历深度压到了可控范围。更稳妥的做法是只要题目给出的节点数可能比较大就默认不能用无脑递归优先考虑迭代写法或者显式栈。这种坑考的不是算法是工程习惯。我建议备考阶段就养成习惯所有树的遍历代码至少准备一套迭代版本作为考场备选。3.3 全局变量没有在每轮输入里重置第四题出现了多组测试数据的情况。我在全局定义了一个vector存储边组与组之间只清理了部分内容没有把边的计数清零结果第二组样例开始答案全错。排查过程很痛苦因为样例第一组是对的第二组错得莫名其妙我一度以为是优先级队列的状态问题。后来我把所有全局变量列了一遍逐个看它们的生命周期才发现问题根源vector.clear()清空了元素但用来做数组下标的计数变量还停留在上一组的末尾导致新数据被追加到老位置后面。这也是PAT特别喜欢考的“阴间细节”多组数据场景下全局变量的生命周期管理。我的改进方式很简单把每一组测试的处理逻辑封闭在一个函数里所有可变状态都作为局部变量重新初始化确实需要用全局数据结构的情况在每组数据开始前集中做一次reset()。宁可多写几行重复代码也不要依赖上一次运行留下的状态。4. 一张从考后复盘倒推出来的备考时间表4.1 第一阶段把常用模板和数据结构磨成肌肉记忆如果你现在距离考试还有十周以上我的建议是把前四周留给基本功而不是急着刷整套卷子。我当时做了两件事一是把线性表、栈、队列、二叉树、堆、哈希表这些结构用C完整手写一遍过程中标注出常用操作的临界情况和返回值比如栈空、堆空、哈希冲突二是把排序、二分、DFS、BFS、Dijkstra、Union-Find这些经典算法的模板整理成一份可以随时查阅的个人速查表。重点不在于背代码而在于理解为什么这么写。每个模板都要回答三个问题时间复杂度是多少什么条件下会退化边界输入会走到哪条分支这个过程是枯燥的但它决定了后期刷题的上限。我在第一阶段结束时常见的建图、遍历、最短路代码已经可以不假思索写出来后面进入真题阶段会顺畅很多。4.2 第二阶段按失分点横向刷题而不是按序号纵刷大多数人的备考误区是“每天限时做一套真题”做完对答案记一下分数就结束了。这种方法效率很低因为一套题里的知识点是混杂的今天做对了一道图论题不意味着下次还能做对很容易产生“我好像都会了”的错觉。我自己更推荐按专题横向刷花两三周时间把同一类考点集中吃透。比如第一周只做树的遍历和重建从已知前序中序推后序、层序的变体全部刷一遍第二周只做图论连通性和最短路的变体第三周集中练习字符串处理和排序题主要为了拿稳第一题。横向刷题的好处是你能清晰看到同类题目的变化规律比如树的重建题核心永远是先找根再递归切分左右子树各种花哨的输出方式只是换皮。这一阶段我还要求自己每道题做完之后用一句话写下“这题考了什么、用了什么结构、容易踩的坑在哪里”期末复盘的时候这些碎片化的总结比任何答案都有用。4.3 第三阶段限时整套模拟只看分数排序考前两周进入整套模拟阶段我每周安排三到四次完整的三小时限时训练。这个阶段的核心不是“刷题量”而是适应考试节奏什么时候该放弃、什么时候该检查、什么时候要加速都需要在模拟中校准。我的个人策略是前90分钟争取写完前三题后90分钟全力冲击第四题如果三小时还剩30分钟且还有题没写完优先把已有代码的边界补完并输出样例而不是继续硬啃新题。整套模拟还有一个作用是训练在时间压力下保持代码整洁的能力。平时练习时变量命名随意点无所谓考场上一旦代码超过两百行混乱的命名会让你排查错误的时间翻倍。4.4 错题本怎么记才有用错题本被很多人记成了“抄题本”抄一遍题目和标准答案之后就再也不看了。我的记录方式是分三栏原题考点、我的错误原因、正确的思考路径。“错误原因”要非常具体比如“递归没考虑空指针导致段错误”而不是笼统写“粗心”“正确的思考路径”要写清楚在读题之后第一步该做什么比如“先判断输入是否可能为空树”或“先检查边是单向还是双向”。每次模拟训练结束后我强制自己把所有错题按这个方法整理一遍。到考前最后一天我不看题只看错题本里的“正确思考路径”栏目快速过一遍所有考点。这个过程比临时抱佛脚刷新题要有用得多。5. 考场上的隐性规则都是白给分和冤枉分的分界线5.1 前二十分钟只做一件事读题很多人在考场上拿到题就开始敲键盘生怕时间不够。我的经验是前二十分钟除了写输入输出模板之外不要急着提交任何东西。把四道题从头到尾读一遍给每道题标注三个属性考点预期、数据范围、可能的坑。这个动作看起来浪费时间实际上能避免你在第二道题上花四十分钟却发现读错题逼得后面兵荒马乱。读题时重点看数据范围节点数是100还是100000决定了算法能不能接受O(N^2)的复杂度输入是否可能为空决定了要不要做空值判断输出是否要求特定的格式决定了你拼字符串时要不要加额外的分隔符。这些信息都在题面里写得清清楚楚只是考场上容易忽略。5.2 把输入输出优化和代码模板提前备好PAT甲级的题量不大但部分数据规模和输入规模并不算小。如果使用C的cin和cout不做同步关闭在个别数据量大的测试点上确实可能超时虽然不太常见但没必要冒险。我在考前的模板里就固定了这几行#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // ... return 0; }另外我会在考前把图论题的邻接表、树的层序输出、排序算法、并查集这些“大块代码”的结构默写一遍。进入考场之后先花两分钟把常用的数据结构声明和辅助函数写在草稿纸上。真正做题时这些基础结构只需要照着草稿腾挪能节约不少时间。5.3 什么时候该果断放弃一道题考场上的最优策略不是把所有题都写完而是把能拿到的分全部拿稳。我的经验是如果一道题读了二十分钟样例都没搞明白说明你已经掉进了“阅读理解”的坑此时应该跳过去做下一道最后再回头啃。如果一道题写了二十分钟代码超过一百行但样例输出的第一个数字都不对说明模型的某个假设从根上就错了继续改下去大概率是在错误方向上打补丁。放弃一道题不丢人丢分才可惜。我记得自己当时在第四题上卡了将近四十分钟眼看剩余时间不多果断停下把前三题全部重新跑了一遍边界检查确保没有样例之外的细节遗漏然后才回头继续处理第四题。这种“先保基数再冲上限”的策略是我考完复盘认为最正确的决定。写在最后考完PAT甲级的那个下午我把错题本翻了一遍发现丢分最多的其实不是算法难度而是读题粗心、边界疏漏、状态管理这些细节问题。算法能力决定你的上限但这些细节决定你的下限。如果你正在准备下一场PAT我建议你别盲目追求刷题量先耐心把每一个“为什么”搞清楚。这套慢功夫会比考前的临时突击可靠得多。
