因为最近在准备考研，所以一直没机会来总结一下这次的PAT考试，今天抽个空来说说，算是为这几个月来的准备画上一个句号。
我大概算是从去年的十月份开始准备的，初衷是为了在大三的最后一段时间多参加一些比赛，避免考研进了复试后简历上奖项是空白的尴尬，而且以后机试迟早是要准备的~
当时对于算法和数据结构的代码这些算是零基础，因此买了一本算法笔记开始一步步地学，因为大三上学期的课还是挺多的，所以断断续续到了寒假也才学完了一半，最后一直到寒假结束才勉强刷完了上面的所有题目。
等到考试前才发现自己之前学的又忘了好多，然后花了一天复习一遍那些模板，前几年的真题都还没来得及刷就这样慌慌张张进了考场。
拿到题目先看了第一题心态就崩了，完全没思路，第一题不应该是签到题吗？？？看了五分钟果断翻到第二题，嗯这应该是个时间排序题，算法笔记上练过好多，但是代码好多，先看看下一题。第三题，堆排序！！！还好考前背了一下堆排序的模板，是啥来着，哎一紧张又记不得多少了。先看看最后一题。读了一遍题目，图论的题目，但是好复杂的样子，好像是要用好多次dijkstral最短路径，压轴题先放一放吧。然后我决定先攻破第二题，此时内心差不多已经平静了下来，认真分析了一下第二题，哎这题好像可以用贪心，不管了先试一下，花了20分钟一气呵成写完提交，AC了，NICE！！！25分到手，不至于0分了。此时时间过了差不多40分钟，我手贱点了一下排名，我擦，好多大佬都75分了，心态瞬间又崩了。看了一下这些大佬都是第三题还没有得分，难道这题才是最难的压轴题？然后我看了一下通过率，第四题的通过率居然比其他几题都要高，果断转战第四题。在纸上推演了一遍样例之后，突然发现这题好像floyd算法好像更简单一点，考前刚好有背过这个模板，虽然算法笔记上没有练过floyd的题目，但我还是决定大胆尝试一下，一次AC，太棒了！！！又到手了30分，心情有点好了。此时差不多过了一个半小时，看了一眼排名，我擦，好多大佬已经满分了。接着决定先做第一题，经过40分钟的尝试还是失败了，最后printf大法混了一分。最后开始分析第三题，读了一遍题目好像挺简单的啊，就是对堆排序的一些性质进行判断，然后就开始了艰难地回忆堆排序的模板代码，好在昨天刚看了一遍有点印象，最后成功写了出来。但是这时候题目对输入的判断又难住了我，只好用最笨的方法来慢慢分割，然后发现考点的devC++居然用不了C++11，好坑啊，只好放到考试端去测试，因为不能debug又浪费了好多时间，最后好在是在结束前10分钟拿下了24分，总分80，对我来说非常满意了，算是超常发挥了。
下面贴一下题目和代码
第一题
第一题就算了，只拿了1分，还是printf混到的
第二题
#include <cstdio>#include <algorithm>using namespace std;const int MAXN = 3000;struct Time{int Shh, Smm, Sss;int Ehh, Emm, Ess;}time[MAXN];int n;bool cmp(Time t1, Time t2){if(t1.Ehh != t2.Ehh) return t1.Ehh < t2.Ehh;if(t1.Emm != t2.Emm) return t1.Emm < t2.Emm;if(t1.Ess != t2.Ess) return t1.Ess < t2.Ess;}bool g(Time t1, Time t2){if(t1.Shh > t2.Ehh) return true;else if(t1.Shh < t2.Ehh) return false;else{if(t1.Smm > t2.Emm) return true;else if(t1.Smm < t2.Emm) return false;else{if(t1.Sss > t2.Ess) return true;else if(t1.Sss < t2.Ess) return false;else return true;}}}int main(){scanf("%d", &n);for(int i=0; i<n; i++){scanf("%d:%d:%d %d:%d:%d", &time[i].Shh, &time[i].Smm, &time[i].Sss, &time[i].Ehh, &time[i].Emm, &time[i].Ess);}sort(time, time+n, cmp);int ans = 1;Time temp = time[0];for(int i=1; i<n; i++){if(g(time[i],temp)){ans++;temp = time[i];}}printf("%d", ans);return 0;}
第三题
#include <cstdio>#include <algorithm>#include <iostream>#include <string>#include <cstring>using namespace std;const int MAXN = 1100;int n, m;int heap[MAXN];int num = 1;void upAdjust(int low, int high){int i=high, j=i/2;while(j >= low){if(heap[i] > heap[j]){swap(heap[i], heap[j]);i = j;j = i/2;}else{break;}}}void insert(int x){heap[++num] = x;upAdjust(1, num);}int find(int x){for(int i=1; i<=num; i++){if(heap[i] == x){return i;}}}int main(){scanf("%d %d", &n, &m);scanf("%d", &heap[1]);for(int i=0; i<n-1; i++){int t;scanf("%d", &t);insert(t);}getchar();for(int i=0; i<m; i++){string s;getline(cin,s);if(s.find("root") != -1){int pos;for(int i=0; i<s.size(); i++){if(s[i] == ' '){pos = i;break;}}string res = s.substr(0, pos);if(stoi(res) == heap[1]) printf("1");else printf("0");}else if(s.find("siblings") != -1){int pos1, pos2;for(int i=0; i<s.size(); i++){if(s[i] == ' '){pos1 = i;break;}}string res1 = s.substr(0, pos1);for(int i=0; i<s.size(); i++){if(s[i] == 'r'){pos2 = i;break;}}string res2 = s.substr(pos1+5, pos2-9);int r1 = stoi(res1);int r2 = stoi(res2);int p1 = find(r1);int p2 = find(r2);if((p1/2) == (p2/2)) printf("1");else printf("0");}else if(s.find("parent") != -1){int pos1, pos2;for(int i=0; i<s.size(); i++){if(s[i] == ' '){pos1 = i;break;}}string res1 = s.substr(0, pos1);for(int i=0; i<s.size(); i++){if(s[i] == 'o'){pos2 = i;break;}}string res2 = s.substr(pos2+2, s.size()-pos2-2);int r1 = stoi(res1);int r2 = stoi(res2);int p1 = find(r1);int p2 = find(r2);if((p2/2) == p1) printf("1");else printf("0");}else if(s.find("left") != -1){int pos1, pos2;for(int i=0; i<s.size(); i++){if(s[i] == ' '){pos1 = i;break;}}string res1 = s.substr(0, pos1);for(int i=0; i<s.size(); i++){if(s[i] == 'o'){pos2 = i;break;}}string res2 = s.substr(pos2+2, s.size()-pos2-2);int r1 = stoi(res1);int r2 = stoi(res2);int p1 = find(r1);int p2 = find(r2);if((p2*2) == p1) printf("1");else printf("0");}else if(s.find("right") != -1){int pos1, pos2;for(int i=0; i<s.size(); i++){if(s[i] == ' '){pos1 = i;break;}}string res1 = s.substr(0, pos1);for(int i=0; i<s.size(); i++){if(s[i] == 'o'){pos2 = i;break;}}string res2 = s.substr(pos2+2, s.size()-pos2-2);int r1 = stoi(res1);int r2 = stoi(res2);int p1 = find(r1);int p2 = find(r2);if((p2*2+1) == p1) printf("1");else printf("0");}}return 0;}
第四题
#include <cstdio>#include <algorithm>using namespace std;const int MAXV = 210;const int INF = 1e9;int n, m;int dis[MAXV][MAXV];int sum = 0;bool vis[MAXV] = {false};void floyid(){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][j]>dis[i][k]+dis[k][j]){dis[i][j] = dis[i][k] + dis[k][j];}}}}}int main(){fill(dis[0], dis[0]+MAXV*MAXV, INF);scanf("%d %d", &n, &m);for(int i=0; i<m; i++){int s1, s2, d;scanf("%d %d %d", &s1, &s2, &d);dis[s1][s2] = dis[s2][s1] = d;}floyid();int temp = 0;vis[0] = true;int bh = 0;printf("0");while(1){int MIN = INF;int flag = false;for(int i=0; i<=n; i++){if(dis[temp][i]!=INF && vis[i]==false){if(dis[temp][i] < MIN){MIN = dis[temp][i];bh = i;flag = true;}}}if(!flag){break;}sum += MIN;temp = bh;vis[bh] = true;printf(" %d", bh);}int num = 0;int arr[n];for(int i=0; i<=n; i++){if(!vis[i]){arr[num++] = i;}}if(num == 0){printf("n%d", sum);}else{printf("n");for(int i=0; i<num; i++){printf("%d", arr[i]);if(i != num-1) printf(" ");}}return 0;}