2021年3月春季PAT甲级满分总结（附考场代码）

一、考试经历

本次线上考试100分，一个半小时左右AK（退系统前看了下排名我是第22个满分），四道题分别是dfs、区间贪心模板题、堆、flyod模板题，没有去年那样的坑人题目，算是正常难度吧

考前准备

1月23号结束本科阶段最后一场考试，24号回家，然后就开始第一轮刷题了。题库155道，2月17号结束第一轮，除了一些特别恶心的题目直接扔掉（1082、1119、1052、1056、1057），其他题目都是自己彻底理解弄懂的。如果实在没有思路或者有思路但很繁琐就去看 柳神的代码 学习一些先进STL工具的使用。柳婼的20分代码思路写法堪称一绝，但很多25分和30分的题目你要相信自己能写得更好，特别是一些模拟题，每个人的思考方式都不一样，别人的思路未必适合自己。
第一遍刷题我并不推荐按照题目分类刷，因为这样就锻炼不了分析问题和解决问题的能力，最终只能做一些模板题，稍微变通一下就不知道用什么方法了。比如说同是多条最短路方案找最优解的图论题，有的题目裸DFS就能过，有的必须要Dijkstra+DFS才不会超时（大概题库前面有这样两道题），要思考为什么，下次遇到这种题目要怎么写。
第二遍刷题就可以针对自己的弱点来练习了，第二遍我只做了前面的一部分和 一个宝藏博主的总结 上面的近几年真题。我最惧怕的四个东西：关键路径、AVL树、堆、SPFA，题库里有对应题目的就挑着做，没有的就自己默写算法，保证自己模板题都会做，起码不会遗憾。
3月1号回学校，距离考试还有差不多两个星期，因为平常有睡午觉的习惯，这个时候开始就开始不睡了，并且让自己在1:30——4:30之间保持集中精力做题的状态。花了30块钱买了教育超市的19、20年题目，19年除了9月没有ak其他都是一个半小时内ak，20年题目太离谱了做的我信心暴跌，还好这次没有坑钱的题目。

考前小状况

今年春季开放部分线下考试，看完线上的各种要求之后感觉繁琐且别扭（后来发现其实还挺好的），就打算去浙江唯一的线下考点杭师大考，结果因为想等寒假在牛客网刷完20题领了50元代金券再去报，放假回家时发现杭师大名额已经报满了，那段时间有点想放弃刷题了（因为感觉线上很不靠谱不想去考），好在几天后我蹲到了一个位置，不知道是有人退款还是每周会开放一部分名额，高兴得不行，抢到线下位置了然后就开开心心刷题去。
然鹅在开考前一周，杭师大竟突然通知外校学生不给进校（同是杭州高校生and浙江绿码，有什么不安全的？），这时都已经截止报名好几天了，过几天就考试了不是搞事么？在PAT公众号反映他们机构也没什么办法。

我也很无奈，心态炸了几小时，还是冷静下来立马下单了手机架、钟点房、排插等线上考试配置，花销直接升300+。
不过呢，后面体会了，才发现线上考试似乎更好！可以用自己熟悉的电脑，周围没有人打扰。

线上考试步骤

考前一两天邮箱会收到一个考试登录二维码，考试当天用微信扫码登录双机位监控的小程序，推荐用一个没有好友的微信小号，这样不会被人发消息打扰，手机的铃声、媒体音量调到最大，设置免打扰模式（即不接电话和信息）。关门关窗拉窗帘，拔电话线，然后坐在屏幕前等待，只要考试没开始都可以去上厕所，1：30之前风平浪静的。考试过程中会有一个老师在手机语音找你，让你展示身份证和草稿纸，然后转动手机架，让手机摄像头环绕环境一圈，检查完毕就没事了。
如果提前满分，提前结束考试后就可以关掉监考软件和客户端了。
关于代码调试：推荐用devc++，在编译选项加上"-std = c++11"就能使用各种c++的简洁写法了。样例输入可以在代码同目录下创建一个"in.txt"将样例输进去，在代码的main函数第一行写" freopen(“in.txt”, “r”, stdin) ;", 然后编译运行就不需要在黑框复制粘贴了。
调试我基本都是在本地，考试客户端的编译器也很好用，我第一轮刷题都是用网页上的自定义测试功能做的，但是考试时担心提交人数太多服务器崩就用自己的了。文件最后修改时间差不多就是AC时间了，第一题最难看完直接跳过，等拿下后面的三道题后看到已经5个人满分了，想着第一题应该也不会太难，写了半小时也顺利拿下了。

二、题解（考场原版代码）

1、 Arithmetic Progression of Primes

Problem Description

In mathematics, an arithmetic progression (AP，等差数列) is a sequence of numbers such that the difference between the consecutive terms is constant. In 2004, Terence Tao (陶哲轩) and Ben Green proved that for any positive n, there exists at least one arithmetic progression consists of n consecutive prime numbers. For example, { 7，37，67，97，127，157 } is one solution for n=6. Now it is your job to find a maximum solution for a given n within a given range.

Input

Each input file contains one test case, which gives two positive integers in a line: n (≤10), the number of consecutive prime terms in an arithmetic progression, and MAXP (2≤MAXP<10​⁵​​ ), the upper bound of the largest prime in the solution.

Output

For each test case, if there exists a solution, print in ascending order the prime numbers in a line. If the solution is not unique, output the one with the maximum common difference. If there is still a tie, print the one with the maximum first number. If there is no solution bounded by MAXP, output the largest prime in the given range instead.

All the numbers in a line must be separated by a space, and there must be no extra space at the beginning or the end of the line.

Sample Input 1:

5 1000

Sample Output 1:

23 263 503 743 983

Sample Input 2:

10 200

Sample Output 2:

199

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int n,maxp;
bool vis[maxn]={false}; //true不是素数 
void dfs(int x,int jian,int lvl){if(x<0) return ;if(lvl==n){for(int i=0;i<n;i++){if(i>0) printf(" ");printf("%d",x+i*jian);}exit(0);}if(vis[x-jian]){return ;}else{dfs(x-jian,jian,lvl+1);}
}
int main(){//freopen("in.txt","r",stdin);scanf("%d%d",&n,&maxp);vis[0]=vis[1]=true;for(int i=2;i<=maxp;i++){if(!vis[i]){for(int j=i+i;j<=maxp;j+=i){vis[j]=true;}}}if(n>1){for(int j=maxp/(n-1);j>=1;j--){ //差 for(int i=maxp;i>=(n-1)*j;i--){if(!vis[i]){dfs(i,j,1);}}}}for(int i=maxp;i>=2;i--){if(!vis[i]){printf("%d",i);return 0;}}return 0;
}

2、Lab Access Scheduling

Problem Description

Nowadays, we have to keep a safe social distance to stop the spread of virus due to the COVID-19 outbreak. Consequently, the access to a national lab is highly restricted. Everyone has to submit a request for lab use in advance and is only allowed to enter after the request has been approved. Now given all the personal requests for the next day, you are supposed to make a feasible plan with the maximum possible number of requests approved. It is required that at most one person can stay in the lab at any particular time.

Input

Each input file contains one test case. Each case starts with a positive integer N (≤2×10​³​​ ), the number of lab access requests. Then N lines follow, each gives a request in the format:

hh:mm:ss hh:mm:ss

where hh:mm:ssrepresents the time point in a day by hour:minute:second, with the earliest time being 00:00:00and the latest 23:59:59. For each request, the two time points are the requested entrance and exit time, respectively. It is guaranteed that the exit time is after the entrance time.

Note that all times will be within a single day. Times are recorded using a 24-hour clock.

Output

The output is supposed to give the total number of requests approved in your plan.

Sample Input:

7
18:00:01 23:07:01
04:09:59 11:30:08
11:35:50 13:00:00
23:45:00 23:55:50
13:00:00 17:11:22
06:30:50 11:42:01
17:30:00 23:50:00

Sample Output:

5

Hint：

All the requests can be approved except the last two.

AC代码

#include<bits/stdc++.h>
using namespace std;
struct node{int in,out;
};
bool cmp(const node &a, const node &b){return a.out!=b.out ? a.out<b.out : a.in>b.in;
}
int main(){//freopen("in.txt","r",stdin);int n,h1,m1,s1,h2,m2,s2,sum=1;scanf("%d",&n);vector<node>a(n);for(int i=0;i<n;i++){scanf("%d:%d:%d %d:%d:%d",&h1,&m1,&s1,&h2,&m2,&s2);a[i].in=h1*3600+m1*60+s1;a[i].out=h2*3600+m2*60+s2;}sort(a.begin(),a.end(),cmp);int last=a[0].out;for(int i=1;i<n;i++){if(a[i].in>=last){sum++;last=a[i].out;}}printf("%d",sum);return 0;
}

3、Structure of Max-Heap

Problem Description

In computer science, a max-heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree.

Your job is to first insert a given sequence of integers into an initially empty max-heap, then to judge if a given description of the resulting heap structure is correct or not. There are 5 different kinds of description statements:
x is the root
x and y are siblings
x is the parent of y
x is the left child of y
x is the right child of y

Input

Each input file contains one test case. For each case, the first line gives 2 positive integers: N (≤1,000), the number of keys to be inserted, and M (≤20), the number of statements to be judged. Then the next line contains N distinct integer keys in [−10^​4​​ ,10​⁴​​ ] which are supposed to be inserted into an initially empty max-heap. Finally there are M lines of statements, each occupies a line.

Output

For each statement, print 1if it is true, or 0if not. All the answers must be print in one line, without any space.

Sample Input:

5 6
23 46 26 35 88
35 is the root
46 and 26 are siblings
88 is the parent of 46
35 is the left child of 26
35 is the right child of 46
-1 is the root

Sample Output:

011010

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int h[maxn],n,m,key,inh=0;
unordered_map<int,int>ump;
void update(int low,int high){int i=high,j=high/2;while(j>=low){if(h[i]>h[j]){swap(h[i],h[j]);i=j;j=i/2;}else{break;}}
}
int main(){//freopen("in.txt","r",stdin);scanf("%d%d",&n,&m);string s,ans="";for(int i=0;i<n;i++){scanf("%d",&key);h[++inh]=key;update(1,inh);}for(int i=1;i<=n;i++){ump[h[i]]=i;}getchar();for(int cnt=1;cnt<=m;cnt++){getline(cin,s);stringstream ssin(s);string t;vector<string>ddd;while(ssin>>t){ddd.emplace_back(t);}int x,y,dx,dy;if(ddd.back()=="root"){if(stoi(ddd[0])==h[1]){ans+='1';}else{ans+='0';}}else if(ddd.back()=="siblings"){x=stoi(ddd[0]);y=stoi(ddd[2]);dx=ump[x];dy=ump[y];if(dx/2 == dy/2){ans+='1';}else{ans+='0';}}else{x=stoi(ddd[0]);y=stoi(ddd.back());dx=ump[x];dy=ump[y];if(ddd[3]=="parent"){if(dy/2==dx){ans+='1';}else{ans+='0';}}else if(ddd[3]=="left"){if(dx==dy*2){ans+='1';}else{ans+='0';}}else if(ddd[3]=="right"){if(dx==dy*2+1){ans+='1';}else{ans+='0';}}}}printf("%s",ans.c_str());return 0;
}

4、Recycling of Shared Bicycles

Problem Description

There are many spots for parking the shared bicycles in Hangzhou. When some of the bicycles are broken, the management center will receive a message for sending a truck to collect them. Now given the map of city, you are supposed to program the collecting route for the truck. The strategy is a simple greedy method: the truck will always move to the nearest spot to collect the broken bicycles. If there are more than one nearest spot, take the one with the smallest index.

Input

Each input file contains one test case. For each case, the first line contains two positive integers: N (≤ 200), the number of spots (hence the spots are numbered from 1 to N, and the management center is always numbered 0), and M, the number of streets connecting those spots. Then M lines follow, describing the streets in the format:

S1 S2 Dist

where S1and S2are the spots at the two ends of a street, and Distis the distance between them, which is a positive integer no more than 1000. It is guaranteed that each street is given once and S1is never the same as S2.

Output

For each case, first print in a line the sequence of spots in the visiting order, starting from 0. If it is impossible to collect all the broken bicycles, output in the second line those spots that cannot be visited, in ascending order of their indices. Or if the job can be done perfectly, print in the second line the total moving distance of the truck.

All the numbers in a line must be separated by 1 space, and there must be no extra space at the beginning or the end of the line.

Sample Input 1:

7 10
0 2 1
0 4 5
0 7 3
0 6 4
0 5 5
1 2 2
1 7 2
2 3 4
3 4 2
6 7 9

Sample Output 1:

0 2 1 7 6 3 4 5
33

Sample Input 2:

7 8
0 2 1
0 4 5
0 7 3
1 2 2
1 7 2
2 3 4
3 4 2
6 5 1

Sample Output 2:

0 2 1 7 3 4
5 6

AC代码

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 201;
int dis[maxn][maxn],vis[maxn],n,m,u,v,w,sum=0;
vector<int>path,lost;
void run(int s){path.emplace_back(s);vis[s]=1;int p=-1,minl=INF;for(int i=0;i<=n;i++){if(!vis[i] && dis[s][i]<minl){minl=dis[s][i];p=i;}}if(p==-1) return;sum+=minl;run(p);
}
int main(){//freopen("in.txt","r",stdin);for(int i=0;i<maxn;i++){for(int j=0;j<maxn;j++){dis[i][j]=INF;}}memset(vis,0,sizeof(vis));scanf("%d%d",&n,&m);for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&w);dis[u][v]=dis[v][u]=w;}for(int k=0;k<=n;k++){for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){if(dis[i][k]!=INF && dis[k][j]!=INF && dis[i][k]+dis[k][j]<dis[i][j]){dis[i][j]=dis[i][k]+dis[k][j];}}}}run(0);for(int i=0;i<path.size();i++){if(i>0)printf(" ");printf("%d",path[i]);}printf("\n");for(int i=0;i<=n;i++){if(vis[i]==0){lost.emplace_back(i);}}if(lost.size()==0){printf("%d",sum);}else{sort(lost.begin(),lost.end());for(int i=0;i<lost.size();i++){if(i>0)printf(" ");printf("%d",lost[i]);}}return 0;
}

三、总结

努力一定会有收获，如果再加上一点运气，那么结果也会是好的。PAT考试就和摸奖似的，时而简单时而难，保证自己《算法笔记》上大纲里的知识点都熟练掌握了，再强化一下分析问题的能力，谨记穷则变，变则通，相信是一定能AK的。
如果不行，那就下次再战！