PAT甲级准备历程及经验教训总结

这篇文章主要写给不知道如何开始准备PAT的朋友们~算是我自己的一点小小的感想吧！

大概是在2019年底或者2020年初报名了2020年的春季PAT，本来是在3月份进行考试，结果因为今年的特殊情况一直推迟到了2020年7月25日，最终考试成绩为91分，虽然没有达到满分，但是也积累了一些经验和教训。所以想在这里进行一些分享。

一、我的个人情况

我是浙大数字媒体技术专业倒数第二届的学生，算是和计算机沾边，因为之前修过数据结构（但都是去年的事了），所以有一定的数据结构和算法知识的基础，水平大概在记得有这么个关键词，比如你告诉我快排/堆/树/图，我会知道我学过这么个东西，但具体再问可能就说不太清了。 说这么多的意思大概就是：我是个非常非常普通的人，脑子没有特别好但也不算差，基础说有也有，但是时隔久远也快忘得差不多了。 如果你和我情况一样不知道怎么开始的话就看下去吧~

二、准备PAT的时间线

2~4月：放寒假在家一个多月+开学一个多月，由于寒假前的考试周元气大伤所以一直没太缓过劲来，寒假没有怎么刷过，之后也因为刚开学需要准备的事情比较多搁置了5月：学校开放了第一批返校，在五月上中旬的时候回到了学校，学习的时间和效率都大幅度提高。不过这段时间也是最痛苦的阶段，因为刚开始刷题不知道应该以什么顺序，以及对于数据结构和算法的记忆已经基本消失了……刚开始刷题非常艰难，但是还是保持着每天刷3~5道题，刚开始要用五六个小时，后来用一个上午差不多能结束当日PAT工作，到五月底一共AC了差不多55道题左右。差不多算是把C++的应用基础打了一下。总结一下，5月我所做的事情： 把柳神的C++教程看了几遍，弄懂了C++的基本操作（实不相瞒，当时对于STL也记不大清了…）刷题的时候参考晴神的《算法笔记》（强烈推荐！！！书里对于数据结构的讲解非常清晰易懂，并且总结的题型也很全面），按章节一点一点来按部就班地做。 6月：学校的考试周大作业一个一个一个一个一个一个一个一个一个一个一个一个一个一个一个来了，秃头一个月，刷的题不超过10道7月：学校的考试周大作业一个一个一个一个一个一个一个一个一个一个一个一个一个一个一个做完了，开始去之前联系的导师实验室学习，每天上午到实验室，午休的时间刷1-2道题，晚上回到寝室再刷2-4道题，但是一般情况下坐89路回玉泉之后我一般筋疲力竭，大概工作日每天维持在最少3道，最多6道（这一般就是赶巧那天的题都不难且运气好）的数量。周六日休息日刷题比较多，从早到晚能刷十几道题。这段时间是掌握数据结构和算法的时期，其实做多了题会发现其实PAT的套路基本是差不多的~这段时间还是跟着《算法笔记》在做题，觉得书上给出来的某一小部分示例代码长不想看的人（比如我）可以去柳神的博客上面看看，无论是《算法笔记》上的代码思路还是柳神的思路都能令人狂拍大腿称妙（我怎么就没有这种脑子！！！）考试：在考试之前刷完了绝大部分的重点考点，一共刷了124道题，当然我没刷完还是有一点点小慌。。。然后考试前几天还看到姥姥微博下面说“今年考题会出一些非模板题”，我慌上加慌，因为感觉PAT上刷到的模板题还蛮多的，弄懂一个知识点多做几道题就能看出来的那种…于是怀揣着忐忑和紧张的心情我赶走了室友 独自坐在寝室等待线上考试的开始，深呼吸7861686532次后开始了考试。

总的来说一共刷题的天数大概在40-50天左右，每天大概五个小时左右~

三、考试经过（此处有些混乱，随便看看就好）

开始考试后，激动的心，颤抖的手，我颤巍巍地点开了第一道题。大概知识点是处理字符串将其变成数字然后判断素数的一个问题，我快马加鞭，劈里啪啦打出来了第一题的答案，用时7分钟。做完第一题我心想：我也太牛了！！！！！！！！！！！（考试就是要这样激励自己哈，因为我感觉做完第一题之后我的紧张情绪大降）

第二题是一道应用了各种存储方式的题，但是迄今我也想不出来考到了什么明显的知识点。。大概题意是每个人依次给出一个数，这个数必须是前面人给出来的所有数字中的两个数字之差（大概是这样，我也忘得差不多了…），它难就难在数据的存储和调用有一点费劲，最后吭哧吭哧花了半个多小时搞出来超时了2个测试点，愣了5秒决定先做下一题。

遂转战第三题，第三题好像是一道并不典型的图（救命，我真的想不太起来了），但是不难，大概二十多分钟AC掉了。

战第四题，第四题是一个NP Complete问题的模拟，学过ADS的同学可能知道，关于external sorting，做了半天出来就过了一个点？

这时的我知道了什么叫做：模板题会少一点（这根本就是没有好吗55555555555……）最重要的是此时我所有的点错误原因均是四个绿绿的大字：运行超时。此时距离考试结束还有1.5个小时，当时得分大概83分左右，我寻思这不行啊，白刷这么多道题了？

于是我做了最正确的一个决定：回去磕第二题。第二题的运行超时总结起来应该是我每次判断数字是否是之前数字的差的时候都会扫描一遍之前存储数据的vector，每次都扫描一遍就变成了O(n²)，当数据量巨大的时候会导致非常慢，运行超时。于是我建立了一个bool数组，用来存储这个差是否可能会存在，每次输入一个值的时候就把所有可能的差值都设为true，之后直接判断即可，这时再提交答案就变成了全部正确，此时我获得了88分。

然后我回去死磕第四题，最后不知道为什么（是真的不知道为什么）有一个点不超时了……这个时候成绩成了91分，后面就再也de不出来bug了……了……

四、考场经验及教训

总体来说，这次虽然没有得到满分，但是自我感觉91分也还算对得起这几个月吧！（毕竟我只是一个菜菜的人）接下来说一下经验教训啦~

经验

开始的时候最好不要上来就刷题（因人而异，如果基础不好的话不要上来就刷题，越刷越懵，做出来了也不知道到底考察什么知识点），可以先学习一下C++的特性，打好基础，以后用map，vector这些的时候才能更得心应手一些。晴神的《算法宝典》和柳神的博客一生推！自我感觉按照题型进行刷题的时候可以更好地了解这个题型的特点，总结出规律。在按照题型进行刷题的时候慢慢的就可以总结出大概的思路流程啦！题嘛，都是越刷越熟练的~如果时间充裕的话可以按照《算法笔记》从头到尾跟一遍，因为书里面囊括了前一百多道，后面新出的五十多道是没有的，所以可以先跟着书里走一遍，把所有的知识点都吃透了之后，再按顺序做后几十道。也可以四道四道计时做，比如1152-1155一共四道题一起做，定时三个小时，模拟考试。如果时间不充裕的话，就从《算法笔记》中每个题型里面调几道题做一下，知道了大概思路套路就好了！在刷题的时候，可以把自己经常注意不到的点记录下来，比如边缘数据的处理、特殊情况的考虑等等，遇到答案错误可以先看看是不是这些错误，如果实在想不起来也不要死磕，看看别人的成功代码，找找自己的问题~

教训

前面也提到，第一遍顺完四道题之后所有的错误点都是运行超时，而我对这样的错误简直束手无策，因为之前刷题的时候很少遇到这样的情况，基本都是答案错误，这也就提醒了我之前刷题的时候基本没有注意过算法复杂度的分析和优化，基本上都是做出来答案正确就接着下一道了，没有怎么思考过怎么优化它才能让代码变得更简洁、时空复杂度最低。这个方面以后可以改善！多多向大佬们学习！

心态

在心态方面，不用太紧张啦！只要好好准备都是可以的！一直刷不过去的时候也不要怀疑人生！看懂吸收别人的思路和风格，内化为自己的东西，慢慢积攒，都是可以的！

以上均为自己个人观点，请谨慎参考~ 预祝大家都考到满意的PAT成绩~~