如何一个月左右拿下PAT甲级（浙大机试）满分 |
您所在的位置：网站首页 › 如何准备大学考试 › 如何一个月左右拿下PAT甲级（浙大机试）满分 |
如何一个月左右拿下PAT甲级（浙大机试）满分
|
说明：本经验适用于PAT甲级难度（包括浙大保研机试、考研复试机试） 博主情况： 双非，无任何ACM经历，浙大保研机试满分（PAT甲级难度）。19年8月初开始准备机试，9月初考了秋季的PAT甲级，没过90感觉不够，9月中下旬参加浙大保研机试（同样是甲级难度），1个半小时左右拿下满分。 前期准备：编程语言首选C++，要熟悉1-2个编译器，我用的是dev C++，要注意不同考场提供的编译器不同，需要提前上官网了解好，比如浙大紫金港是这次是没有VS的，因此一般来说练dev或者code blocks比较保险。 辅助材料强烈推荐两本书： 《算法笔记》（胡凡、曾磊主编）以及对应配套的《上机实战指南》《王道论坛计算机考研机试指南》第一本书又称晴神宝典，主要就是针对PAT编写的，对于没接触过ACM的人来说简直是相见恨晚，按照题型专题讲解，还给出各类题型的模板套路，以及常用STL的用法，能帮你节约大量时间。 第二本多年前就停更了，最新的13年的pdf版，不过机试也就那些东西，跟现在也区别不大。网盘下载 提取码: 2vi2 接着是考点，总体来说经过训练后，甲级并不算难，很多东西已成了模板套路了。我们来看看要求（节选自官网） 乙级（Basic Level）：一句话概括，最难到排序 甲级（Advanced Level）：在达到乙级要求的基础上，还要求： 1· 具有充分的英文阅读理解能力； 2· 理解并掌握基础数据结构，包括：线性表、树、图； 3· 理解并熟练编程实现经典高级算法，包括哈希映射、并查集、最短路径、拓扑排序、关键路径、贪心、深度优先搜索、广度优先搜索、回溯剪枝等； 备战要点：1.刷真题。最简单粗暴的方法，把官网上的真题库通刷一遍，150+道题，一开始刷的可能会有点慢，一天3-4题，到后面熟练以后6-10题一天。另外，题库里前半部分里有些题是超纲的，发现特别难也不需要纠结。（1069以后应该都是真题了）
2.背模板。其实PAT考来考去也就那么几种类型的题，常用的算法和语法模板背一下，最重要的包括 自定义 STL中的sort规则，知道如何给结构体数组排序vector, stack, queue, map等库的常规用法并查集及路径压缩Dijkstra最短路径算法（常规版+DFS版）Hash表的查找模拟及hash冲突解决模拟DFS，BFS二叉树的遍历（前中后序+层序）二叉树的重建（如根据前序+中序）AVL树的判断（树的构造能写更好，不过感觉略难，考的几率不大）数学类（素数判断、最大公约数、质因子分解等）上述模板《算法笔记》里全都有，且配合例题讲的很清楚。 3.整理题型。PAT甲级总共4道题，刷多了以后会发现题型设置上会呈现出一些规律。其中最简单的两道题就是对应乙级最难的两道题的英文版。我自己尝试总结了一下题型（自己摸索的，不一定准确，只是大概如此） 第一题（20分）常考数学类、逻辑类题目。如涉及到素数、最大公约数，或者自己定义一个规则，让你求或者判断这种特定的数，编程难度低（会写for循环就能做），需要认真读懂题目。建议过样例用时不超过25分钟。第二题（25分）常考简单数据结构及应用。如栈、链表、哈希、结构体等，常见的是排序题，给出一堆数据，按要求排序（链表题本质也是结构体的排序题）。建议过样例用时不超过30分钟。第三题（25分）常考树或图。如二叉树的重建、并查集等套路题的变形，或者是给出一些经典树、图，让你判断（红黑树、拓扑排序、欧拉图等），其实比较简单，别被吓到，根据定义来就行。建议过样例用时不超过30分钟。第四题（30分）常考树或图。如最短路径、最近公共祖先、堆的判断等。这类题目往往也不难，但一般代码量较大，很可能需要DFS及剪枝。建议过样例用时不超过1小时。我们看真题库里的最后三组题（1144~1155）来验证一下，发现规律大致如此 20分题：1144简单数学逻辑；1148狼人杀逻辑题；1152素数题25分题：1145Hash冲突题；1149map题；1153排序题；25分题：1146拓扑排序简单判断；1150旅行商问题（简单判断）；1154图着色问题30分题：1147堆的判断；1151最近公共祖先；1155堆的判断+DFS另外，上面建议的用时都是过样例的时间，不是完整AC的时间，毕竟PAT是按测试点给分，而我们的目标是尽可能地多得分，这时候做题策略就显得很重要：比如20分的题卡住了，可能需要花上30分钟才能拿满20分，但可能只需要花15分钟写一个不完美的代码就能拿16分，这时候就要果断放弃，及时转到下一题。当四道题都过了样例，起码有七八十分了，最后半个多小时再回头查漏补缺，争取上90甚至满分。一般来说，不管是保研、考研还是就业，甲级90+都是一个非常不错的成绩了。 刷题技巧和注意点：1.编译器允许的情况下，可以借助C++11来简化代码。C++11中有很多好用的东西，比如整数型和string型的相互转换等等，都有了预设的函数可以直接调用。如何开启C++11网上都有教程，比如DevC++可以看这篇https://blog.csdn.net/Imagirl1/article/details/82707672。（注意！dev 要5.11以上版本才支持C++11，要注意考场提供的版本号，比如浙大紫金港的dev是5.10，是不支持C++11的）。 2.通过输入重定向从文件中读input，可以避免每次手动向控制台中复制粘贴数据的麻烦。在代码所在文件夹中新建一个input.txt文本文件，然后把输入数据复制进去，接着在代码里加两句代码，运行的时候就会自动输入啦，非常方便！！下面给出一个输入模板，考试前可以先把模板敲好再点“开始考试“的按钮，节省一两分钟的时间。 #include #include //需要引入的库 using namespace std; int main(){ freopen("input.txt","r",stdin); //提交时把这行注释掉就行 /* coding... */ return 0; }3.printf也能输出string。我们都知道string数组贼好用，但缺点是只能用cin和cout，输入输出速度慢，有可能最后一个大数据测试点就卡超时了。但实际上，pirntf也是能输出string的，只需要借助函数c_str()，就能将string转化成字符数组。 string s = "Hello World"; printf("%s", s.c_str());4.读行之前如果出现过cin或scanf，一定要把最后一个回车换行给吞掉，不然输入会出错 /* 如输入为： 2 Aplle is red. Banana is yellow. */ int a; string s1,s2; //这段读输入的代码是错误的，banana那行不能正常读入 scanf("%d", &a); getline(cin, s1); getline(cin, s2); //正确代码1 scanf("%d", &a); getchar(); //把换行给“吞掉” getline(cin, s1); getline(cin, s2); //正确代码2 scanf("%d\n", &a); //加上\n回车符，这样也能跳过 getline(cin, s1); getline(cin, s2);5.刷完之后可以看看别人的博客和代码，看看有没有更简单的方法做，开拓一下思路。 6.rounded up是四舍五入的意思，不是向上取整 7.题目中如果出现long int，其实就是int的意思 8.开数组要开在main函数外面，另外数组不能开得过大，比如10000*10000的二维数组绝对内存超限了，1000*1000左右的没问题 补充：条件允许的话，尽量多报几次PAT，多几次机会嘛，考试这玩意，也看考试时候的发挥和心态，谁也说不准。（就像我考PAT的时候，中途就蓝屏了，后来重登又进不去系统。。） 牛客网有个福利，刷20道题可以领50元代金券，还是很棒的。代金券活动
|
【本文地址】