作为一个绩点不高、牌子不硬的退役ACMer，去年冬天在nvpy的鼓励下，决定先试试PAT为考研做准备，于是认认真真把所有20分的题目过了一遍。放寒假以后，就开始练习所有25分的题目，并且每道题做完都总结了博客，供别人学习，也供自己复习。结果时间安排上出现了问题，导致后面没有太多时间写程序，整个2月份到今天，没写过一行代码（大家参与程序设计考试一定要避免这种行为）考试竟是第一次打开编译器写程序。。。最后没能把PAT题库刷一遍，然后将每道题的高质量题解做出来也是PAT考试中的一个遗憾吧。
根据个人做PAT题库的经历，对于还在备考PAT的同学给出以下建议：
认真阅读题目，不放过每一个单词，并且一定要注意题目的数据范围，多考虑边界条件。思维一定要缜密，书写代码时保持思路清晰和大脑冷静。对于一些常见的术语单词要理解，否则影响理解题意。熟练掌握STL、暴力、贪心、字符串处理、基础数据结构（并查集、二叉树）、简单数论（GCD、欧拉筛等基础知识）、基础图论（dfs、bfs、最短路、拓扑排序）等知识。总体来说，PAT甲级不需要多么高深的算法知识和数据结构，但是会着重考察个人的思维能力和基础知识。因此在平时的训练中应该多做简单题目，提高码力、改善思维。
这次的题目难度应该是比较适中的，没有很多的坑点，英文也能读懂（这很重要！！！）。
第一题
题意：给出n和m，找出由n个不超过m的素数组成的等差数列，若找不到，则输出不超过m的最大素数。
思路：筛出不超过m的所有素数，然后暴力遍历即可。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <algorithm>using namespace std;const int N=1e5+5;int prime[N],ans[20];int n,m,lim;vector<int> v;void setv(){ prime[0]=prime[1]=1; for(int i=2;i<=m;i++) if(!prime[i]){ v.push_back(i); for(int j=i+i;j<=m;j+=i) prime[j]=1; }}bool judge(int i,int j){ int dif=v[i]-v[j]; for(int k=0;k<n;k++) if(v[i]-dif*k<0||prime[v[i]-dif*k]) return false; return true;}int main(){ scanf("%d%d",&n,&m); lim=m/n; setv(); int dif=-1; for(int i=v.size()-1;i>=0;i--){ for(int j=i-1;j>=0;j--) if((v[i]-v[j]>dif||(v[i]-v[j]==dif&&v[i]-dif*(n-1)>ans[0]))&&judge(i,j)){ dif=v[i]-v[j]; int cnt=0; for(int k=n-1;k>=0;k--){ ans[k]=v[i]-dif*cnt; cnt++; } } } if(dif!=-1) for(int i=0;i<n;i++) printf("%d%c",ans[i],i==n-1? 'n':' '); else printf("%dn",v[v.size()-1]); return 0;}
第二题
题意：给出一天内n个人进出实验室的时间，在保证同一时刻实验室只能有一人工作的情况下（前一人离开的时间可以和后一人进入的时间相同），求这天最多可以让几个人进入实验室工作。
思路：将所有时间换算成秒为单位的整数，然后按照出实验室的时间递增进行排序即可。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=2e3+5;struct Node{ int st,en;} per[N];int gettime(int hh,int mm,int ss){ return hh*60*60+mm*60+ss;}bool cmp(const Node &a,const Node &b){ if(a.en==b.en) return a.st<b.st; return a.en<b.en;}int main(){ int n; scanf("%d",&n); for(int i=0;i<n;i++){ int hh,mm,ss; scanf("%d:%d:%d",&hh,&mm,&ss); per[i].st=gettime(hh,mm,ss); scanf("%d:%d:%d",&hh,&mm,&ss); per[i].en=gettime(hh,mm,ss); } sort(per,per+n,cmp);// for(int i=0;i<n;i++)// printf("%d %dn",per[i].st,per[i].en); int ans=0; for(int i=0;i<n;i++){ int pre=per[i].en,cnt=1; for(int j=i+1;j<n;j++){ if(per[j].st>=pre){ cnt++; pre=per[j].en; } } ans=max(ans,cnt); } printf("%dn",ans); return 0;}
第三题
题意：首先将给出的n个数字按照输入顺序构造一个大顶堆，然后依次判断给出的m个询问是否正确。询问内容包括：a是否为根、a和b是否为兄弟节点、a是否为b的左子节点，a是否为b的右子节点、a是否为b的父节点。
思路：从无到有构造大顶堆，其在任何时刻都满足完全二叉树，因此可以使用数组来存树，即根节点的下标为1，第i个节点的左子节点下标为i<<1，右子节点下标为i<<1|1，然后对于每次插入逐层更新到根节点即可。由于询问给出的是每个节点的值，因此在最大堆生成后，可以使用一个map来记录每个节点的值与其下标的映射关系。最后按照询问内容，进行判断即可。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <sstream>#include <map>using namespace std;const int N=1e3+5;int tr[N];map<int,int> mp;void update(int i){ while(i!=1&&tr[i]>tr[i>>1]){ swap(tr[i],tr[i>>1]); i=i>>1; }}int main(){ //freopen("input.txt","r",stdin); int n,m,a; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a); tr[i]=a; update(i); } for(int i=1;i<=n;i++) mp[tr[i]]=i; string s; getline(cin,s); for(int i=0;i<m;i++){ getline(cin,s); //cout<<s<<endl; stringstream ss(s); int a,b; string op; ss>>a>>op; if(op=="and"){ ss>>b; int ida=mp[a],idb=mp[b]; if((ida%2==0&&idb==ida+1)||(idb%2==0&&ida==idb+1)) printf("1"); else printf("0"); } else{ ss>>op; ss>>op; if(op=="root"){ if(mp[a]!=1) printf("0"); else printf("1"); } else if(op=="parent"){ ss>>op; ss>>b; if((mp[b]>>1)!=mp[a]) printf("0"); else printf("1"); } else if(op=="left"){ ss>>op; ss>>op; ss>>b; if(mp[a]!=(mp[b]<<1)) printf("0"); else printf("1"); } else if(op=="right"){ ss>>op; ss>>op; ss>>b; if(mp[a]!=(mp[b]<<1|1)) printf("0"); else printf("1"); } } } printf("n"); return 0;}
第四题
题意：给出n个结点（1~n）和m条路径，卡车从0号节点开始，保证每次都前往距离最近且未曾走过的结点（若距离相等，则去编号较小的点）。将所有能够到达的点全部遍历一次后，求遍历的顺序。如果可以将n个结点都遍历一次，求卡车所走的总路程，否则按照编号递增的顺序将没有遍历的结点输出。
思路：使用并查集可以求出能够到达的结点。使用Floyd可以求出多源最短路。然后从0号节点开始，按照给定的遍历规则进行遍历即可。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <vector>using namespace std;const int N=2e2+5;const int inf=0x3f3f3f3f;int f[N],g[N][N],vis[N];vector<int> v;int Find(int a){ return f[a]==a? f[a]:f[a]=Find(f[a]);}void Floyd(int n){ for(int k=0;k<=n;k++) for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) g[i][j]=min(g[i][k]+g[k][j],g[i][j]);}int main(){ int n,m; memset(g,inf,sizeof(g)); scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) f[i]=i; for(int i=0;i<m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u][v]=g[v][u]=w; int ru=Find(u),rv=Find(v); if(ru!=rv){ f[ru]=rv; } } int cnt=0; for(int i=1;i<=n;i++){ if(Find(i)==Find(0)) cnt++; else v.push_back(i); } vis[0]=1; Floyd(n); int ans=0,st=0; printf("0"); for(int i=0;i<cnt;i++){ int to=0,tem=inf; for(int j=1;j<=n;j++){ if(!vis[j]&&g[st][j]<tem){ tem=g[st][j]; to=j; } } ans+=tem; st=to; vis[st]=1; printf(" %d",st); } printf("n"); if(cnt<n) for(int i=0;i<(int)v.size();i++) printf("%d%c",v[i],i==(int)v.size()-1? 'n':' '); else printf("%dn",ans); return 0;}