2019年秋季PAT甲级复盘+总结
这次PAT甲级总体来说还是偏简单的，没有特别坑的测试点，也算是运气比较好，顺利的拿到满分，可以全力备战了。在这里简答分享一下当天的流水，以及对PAT甲级考试的一些心得体会。
考场
由于报名的比较晚了，杭州除了传媒已经没有多余的场地，遂只能选择在下沙传媒学院考试，事实上如果愿意承担风险的话，完全可以等到截止报名前几天，此时会有很多学生退考，多关注报名页就可以抢占到玉泉校区的位置。
到传媒是12点左右，来到生活区的美食广场，已经物是人非，爱吃的店面都已经搬走了，只剩下干锅的店面还在，但是老板也已经换过了。正直学生军训的时候，到处都是军训的学生和教官，到了现教5楼才见到了众多前来考试的考生，心情不免开始紧张起来，粗略的观察一下，大部分考生都是98~99年的，不免感叹老矣。
考试过程
上机看了下环境Dev-C++、VC2010、Eclipse、PyCharm，环境还是比较齐全的。开始考试，粗略的看了下第一题，最大公约数加3000ms的时限，心里感到一阵凉凉，辗转相除法已经忘记了，不知道推不推的出来，于是直接跳过。
第二题Merging Linked Lists，心里感到一喜，类似的题目题库里出现过很多了，例如1052 Linked List Sorting，1074 Reversing Linked List，1097 Deduplication on a Linked List，考前一天还刷过一道，码字、提交、一次过，唯一感到一点的不爽的就是VC2010的代码格式化功能比较弱，例如for(int i=0;i<count;i++并不会格式化为for(int i = 0; i < count; i++)，算是逼死我这个强迫症了。
第三题Postfix Expression，改编自2017年考研408真题，真题求得是中缀表达式，题意很好理解，变形的二叉树后续遍历，码字调试，但是只要执行到std::string text; std::cin >> text;必定会产生异常，不知道是VS2010的原因，还是msvc编译器的原因，平时练习使用macOS + VS Code + clang + lldb，完全没有想到会有这种情况。写个简单的后序遍历，直接提交，过了一个点，把没有左子树的情况加上，Lucky，直接过。瞄了眼右边的哥们还在调第一题，看样子跳过第一题是个明确的选择。
第四题Dijkstra Sequence，判断给定序列是否可能是Dijkstra寻找顶点的序列，直接码字，加点判断条件，竟然一次过，这题30分比较水，最简单的Dijkstra算法，完全不用考虑多条件的判断。此时看了下时间60分钟，当时的排名和另一个考生并列第一。
回到第一题Forever，仔细看了下题目，发现最多只会求到89的最大公约数，内心已经止不住的开始膨胀，码字，竟然只过了第一个点，果然第一题一般是最坑人的，最后一题是最水的。重新看下题目，发现漏了一个条件，求的是大于2的质数，需要把2排除，补上判断，纳尼只过了前两个点。此时已经有考生拿到满分了，开始无尽的焦虑，在优化了公约数的算法，将整体算法从递归改为迭代等等尝试后，仍然没有头绪，此时离做完后3题已经80分钟过去了，难道又要报名冬季的PAT了吗。冷静下来重新读了下题目，发现最后的结果要排个序，套个map提交，过了前三个点，剩下最后一个超时。思考一下，剪枝将不可能的情况下直接排除，直接过，4个点耗时居然都小于10ms。
至此拿到了满分，提前了半小时完成，同个考场有一个哥们大概比我快了20分钟。据说后面服务器还崩溃了，延长了考试时间。
考试的代码位于我的Github仓库。
考试心得
这次考前大概刷了50道题，题库还剩30题，准备的不多，题库里有个哥们刷了5遍题库。这次甲级偏简单，相比于上一次的难度少很多，除了第一题几乎没有坑的测试点，其实第一题也不算特别坑，也没有题意复杂的题目，如果后三题即使某一道有坑，我可能也没时间调第一题了。回想今年春季的考试，前三题每一道题到最后都有一个点过不去，手动捂脸。据姥姥的微博，本场有154个满分，3900+的报名，但是证书上只显示了2600+，也就说有1300个人直接白给，白送30万，不过考场上确实有很多空位子。
考试趣事
开始考试的时候瞄了一眼左边的哥们，是个93年的，打开了Dev-C开始撸代码。在我做第二题期间，一直唉声叹气，不停的在Dev-C、Eclipse、PyCharm之间轮换使用，每次打开写了两行代码便换下一个IDE。在我做完两题后，这个哥们喊来了老师，要求需要PHP环境，一口老血吐出来，第一次见到用PHP撸PAT的，平时练习居然用的也是PHP，不亏是世界上最好的编程语言，手动狗头，这个哥们可能是个PHP开发。最后老师表示无能为力，让他去另一个教室找主管老师，没想到这个哥们回来以后直接打开了百度搜索C++语法，接着就被系统自动终止考试了，据说老师让他尽力写。
PAT心得
总的来说甲级涉及的都是基本的数据结构，没有涉及特别复杂的算法，有的题目可能需要仔细读题或是仔细分析，部分题目的测试点非常坑人，需要仔细思考每一种情况。强烈建议在中国大学MOOC上学习姥姥的数据结构课程，在练习时，建议自己思考思路，遇到过不了的点，也自己思考没有考虑到的情况，锻炼自己的思维能力。PAT非常爱考两个算法，Dijkstra单源最短路径以及并查集，尤其是并查集，有些题目的题意和并查集完全不相关，但是最后的结果要用并查集处理，树的概念以及树的操作也几乎每次都会出题，需要常练习。
附注
PAT考试从2019年开始，已经不再将真题放入真题题库了，需要在教育超市购买仿真卷，才能提交测试。据姥姥说每次考试的真题将会在2年后，免费开放加入题库。