如何一个月左右拿下PAT甲级(浙大机试)满分_考研复试机试代码能速成吗-程序员宅基地

技术标签: C++算法与竞赛  

说明:本经验适用于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道题,刷多了以后会发现题型设置上会呈现出一些规律。其中最简单的两道题就是对应乙级最难的两道题的英文版。我自己尝试总结了一下题型(自己摸索的,不一定准确,只是大概如此)

  1. 第一题(20分)常考数学类、逻辑类题目。如涉及到素数、最大公约数,或者自己定义一个规则,让你求或者判断这种特定的数,编程难度低(会写for循环就能做),需要认真读懂题目。建议过样例用时不超过25分钟
  2. 第二题(25分)常考简单数据结构及应用。如栈、链表、哈希、结构体等,常见的是排序题,给出一堆数据,按要求排序(链表题本质也是结构体的排序题)。建议过样例用时不超过30分钟。
  3. 第三题(25分)常考树或图。如二叉树的重建、并查集等套路题的变形,或者是给出一些经典树、图,让你判断(红黑树、拓扑排序、欧拉图等),其实比较简单,别被吓到,根据定义来就行。建议过样例用时不超过30分钟。
  4. 第四题(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<iostream>
#include<cstdio> //需要引入的库
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元代金券,还是很棒的。代金券活动

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/xzy5210123/article/details/102681832

智能推荐

Java8 parallelStream——共享线程池对性能解析_jdk8 parallelstream 性能-程序员宅基地

文章浏览阅读3.3k次,点赞2次,收藏8次。最近做压测中发现一个应用中cpu过高,导致接口超时rt情况有些不大稳定,jstack打印线程一直在parallelStream相关的代码出进行计算。故对parallelStream相关做一下研究,找一下优化方法。java8并行流parallelStream,相信很多人都喜欢用,特别方便简单。但是有多少人真正知道里面采用的共享线程池对密集型任务,高并发下的性能影响呢可能你的一个应用里面..._jdk8 parallelstream 性能

C++ 11 创建和使用 unique_ptr_unique_ptr创建空节点-程序员宅基地

文章浏览阅读292次。https://www.cnblogs.com/DswCnblog/p/5628195.htmlunique_ptr 不共享它的指针。它无法复制到其他 unique_ptr,无法通过值传递到函数,也无法用于需要副本的任何标准模板库 (STL) 算法。只能移动unique_ptr。这意味着,内存资源所有权将转移到另一 unique_ptr,并且原始 unique_ptr 不再拥有此资源。我们建议..._unique_ptr创建空节点

NetCoreAPI配置全局路由_selector.attributeroutemodel.template-程序员宅基地

文章浏览阅读853次。1:新增类:RouteConvention,继承自IApplicationModelConvention/// <summary> /// 全局路由前缀配置 /// </summary> public class RouteConvention : IApplicationModelConvention { /// <summary> /// 定义一个路由前缀变量 /// </su_selector.attributeroutemodel.template

算 数-程序员宅基地

文章浏览阅读64次。从woody那里copy一段最简的fib代码[code="ruby"]x,y = 0,1 Array.new(10) {|i| [0,1].include?(i) ? 1 : (x,y = y,x+y)&&(x+y) } [/code]生成了这么多,太多了,中途终止了,不知道多少条。[code="ruby"] 1, 1, 2, ..._359579325206583560961765665172189099052367214309267232255589801

Java的BIO和NIO很难懂?用代码实践给你看,再不懂我转行!-程序员宅基地

文章浏览阅读280次。本文原题“从实践角度重新理解BIO和NIO”,原文由Object分享,为了更好的内容表现力,收录时有改动。1、引言这段时间自己在看一些Java中BIO和NIO之类的东西,也看了很多博客,发现各种关于NIO的理论概念说的天花乱坠头头是道,可以说是非常的完整,但是整个看下来之后,发现自己对NIO还是一知半解、一脸蒙逼的状态(请原谅我太笨)。基于以上原因,..._java bio粘包处理

Python3.9环境搭建RobotFramework_python-3.9.9-amd64用那个版本ride-程序员宅基地

文章浏览阅读9k次,点赞2次,收藏12次。Robot Framework是一个基于Python的,可扩展的关键字驱动的测试自动化框架,用于端到端验收测试和验收测试驱动开发(ATDD)。_python-3.9.9-amd64用那个版本ride

随便推点

Hbase相关操作_hbase 查询-程序员宅基地

文章浏览阅读2.4k次。1.进入shellhbase(main):003:0>hbase shell2.查看所有表hbase(main):003:0> list3.根据rowKey查询某个记录hbase(main):003:0>get '表名','rowKey'4.常用过滤器过滤方式是通过value过滤,匹配出value含7259的数据。scan 'buss_surface', FILTER=>"ValueFilter(=,'substring:7259')"过滤方式是通_hbase 查询

噪声:Practical Poissonian-Gaussian noise modeling and fitting for single-image raw-data-程序员宅基地

文章浏览阅读2k次,点赞4次,收藏16次。Practical Poissonian-Gaussian noise modeling and fitting for single-image raw-data文章目录Practical Poissonian-Gaussian noise modeling and fitting for single-image raw-dataPoissonian-Gaussian ModelingThe Noise Profile AlgorithmWavelet domain analysisSegmentat_practical poissonian-gaussian noise modeling and fitting for single-image ra

计算机开机最快设置,w7提高开机速度如何操作_win7电脑怎么开机更快-程序员宅基地

文章浏览阅读4k次。由于win7电脑使用时间过长或者存放时间久了,难免会出现硬件各方面的老化或者堆积了大量的垃圾,因此就会导致电脑开机时的速度有所降低,对此有些用户就想,在不更换硬件的条件下,有没有方法能够提高一下开机速度,那么win7电脑提高开机速度如何操作呢?这里小编就来告诉大家win7电脑开机更快操作步骤。具体方法:1、在任意界面按下:windows键+R,然后在框内输入msconfig,点确定2、然后选择“启..._如何提高w7系统的开机速度

1688API接口:item_search - 按关键字搜索商品_1688 一件代发 api-程序员宅基地

文章浏览阅读672次。今天分享的是1688平台API,item_search - 按关键字搜索商品接口1688的API开发接口,我们需要做下面几件事情。1)开放平台注册开发者账号;2)然后为每个1688应用注册一个应用程序键(App Key) ;3)下载1688API的SDK并掌握基本的API基础知识和调用;4)利用SDK接口和对象,传入AppKey或者必要的时候获取并传入SessionKey来进行程序开发;5)利用1688平台的文档中心和API测试工具,对接口进行测试。从而了解返回信息,方便程序获取1688_1688 一件代发 api

vue-property-decorator使用指南_vue-property-decorator emit update-程序员宅基地

文章浏览阅读3.1k次,点赞2次,收藏12次。在Vue中使用TypeScript时,非常好用的一个库,使用装饰器来简化书写。一、安装npmi-Svue-property-decorator@Prop @PropSync @Provide @Model @Watch @Inject @Provide @Emit @Component(provided byvue-class-component) Mixins(the helper function namedmixinsprovided byvue-cla..._vue-property-decorator emit update

(七)用ChartDirector绘制实时图表-程序员宅基地

文章浏览阅读467次。本示例演示如何用Web图表控件 ChartDirector 绘制一个配置有刷新率的实时图表。在本例中,由一个计时器驱动的随机数生成器生成新的数据值,新产生的值会转换到数据数组中,然后显示在图表上。图表由一个秒表进行更新,这样图表的刷新率可独立于数据率。此外,这个图表支持暂停以方便用户查看,但是后台的数据仍然在继续更新。图表刷新计时器调用CChartViewer.update..._c++ chartdirect updateviewport