[数据结构与算法]记PAT 甲级 2021年 秋季考试 经验总结、线上考试细节、考场题解

1、简单回顾

今天下午考完了秋季的考试，最终得了97分，第一题扣了3分，非常遗憾。还有一个多小时的时候就已经97了，回来和第一题的剩余3分周旋到最后，没能发现问题所在，不停考虑各种，我觉得可能是陷在已有的题目思维里了。不过也算是给自己在考研时间中花费的准备PAT的时间一个交代。

这次的题目总体来说常规，三四题经典图加树，不像春季那么不常规，没考过的关键路径还是没考

第一题 我没满分，第一题一直没什么类型可言

第二题 应该可以算是考察STL的使用，还有一些sort之类的使用

第三题 一道图的题，我感觉是图的题里比较简单的了，按照题目要求走就行

第四题 树的题，有点新意，需要理解这个树的结构，本质还是树的序列转换

文后会贴出我考场时写的代码。

2、经验总结

稍微总结一下自己做的事情，也给大家一点参考。

很早之前就买了《算法笔记》（还是强烈安利一下），应该是大家都知道的神器。然后我没有专门从头到尾看《算法笔记》，因为是科班然后在备考考研，有些数据结构基础。最主要的工作就是刷题。不过我不是从PAT题集155道从头刷到尾。我采取的方式如下：

1、根据类型刷近年题目（我刷的从1131到1171）可以参考浒鱼鱼前辈的帖子 放个链接在这

刷题的时候整理一下不认识的单词，其实多刷一点就发现就一堆词汇，还有一些小模块，比如素数、gcd之类的，我自己照记忆写了一份不多的，放在这?PAT A 备考实用小模块集合?供大家参考，我的博客也有我刷的题目的题解，附上自己的一点简答解释。

2、从1130开始往前刷，4题一套，我一直刷到了1077，没再往前刷是觉得之前的题目太老了，而且中间考纲也有变化（比如删掉了动态规划），但是如果有时间肯定是做了更好

3、二刷1131开始的题目，到1155，然后去教育超市买题目做，一份5块钱，每份套卷限时仿真。都是最最近年的真题。我觉得是最有价值的题目，因为PAT的命题容易和近年相似。

4、教育超市的题目刷完两次，也差不多快要考试了，我花了点时间进行了点知识总结，帮助自己理清一下自己脑子里各种模块，可以见我的博客。

PAT A 主要数据结构知识点实用模块模板

总结下来还是要多刷题，勤练习，毕竟是实战型的考试，你敲代码，改bug的速度都会影响解题

网上有很多技巧，我觉得关键还是自己试出最习惯的最合适的才是最好的。考试时候和平时几乎是差不多的，养成自己的解题习惯。（比如解题前的准备啊，有限少的输入输出用cin、cout，次数多的用scanf、printf等等等，需要自己做题和总结）

3、线上考试的一些细节

? ? ? ? 我考前非常想知道线上考试的细节，这次自己亲身参与了，也可以和大家分享一下。

????????大概十二点半就可以登录OMS系统了（这个时候要拍照和拍视频，登录之后千万就不能关掉了OMS了），然后再架好手机登录小程序，按照PAT官网的要求即可（记得提前打印一下准考证，登录要用）。然后...我干坐了一个小时，我不知道这里是不是可以上厕所什么的，所以我就提前上了厕所（线上考试中途不允许如厕），硬生生等了一个小时（我觉得1点前应该是可以走动的）。然后这之间我一直没有等到监考员的确认。考到一半才来验证身份，所以也明确了监考员查身份证的时间，是在开考之后，会通过小程序里的麦喊你，然后你要把身份证给到摄像头（我给的是前面电脑的摄像头）。然后我基本都是提前交的解答，就也没有遇到最后卡炸的情况，但是菜到第一题改了一个多小时没有满分。结束或者提前交卷的时候，只要你写的答案都提交过，这个时候点OMS系统的叉叉，输入对应要求的字符（和教育超市考卷形式一样，做过就知道了），就可以退出结束了，然后手机的小程序也可以退了。

? ? ? ? 以上就是线上考试的大致流程，总体来说自己需要准备得充足一些，然后环境和机器自己会比较熟悉，编译器也肯定是平时用的顺手的。（开考之后新建文件都是可以的，不要去打开其他东西就好（除了编译器），登录OMS的时候会检测一次有没有不允许的进程什么的，其他和在PTA系统上做题是一样的，不用太担心）

4、附上自己的考试题解（会比较粗糙）

我的小习惯是写常用的<iostream> <vector> <algorithm> main函数 以及return 0。复制四份

7-1：（没有AC，扣了两个测试点共3分，知道问题的可以指正一下，然后我就要扼腕痛惜了）

我记得考试时候看通过率好像是0.04？是有什么坑吗

经评论提醒，ans的初始值应该是1不是0。考试的时候确实没有想到。可惜了。还是读题不够细致

修改后：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N,K,Sum=0,ans=1;
struct node{
	int add,length;
}Node[10010];
int main(){
	cin>>N>>K;
	for(int i=0;i<N;i++){
		scanf("%d %d",&Node[i].add,&Node[i].length);
		Sum+=Node[i].length;
	}
	for(int i=0;i<K;i++){
		int index;
		scanf("%d",&index);
		if(index>Sum-1){
			printf("Illegal Access\n");
			continue;
		}
		for(int j=0;j<N;j++){
			if(index<Node[j].length){
				printf("%d\n",4*index+Node[j].add);
				if(ans<j+1){
					ans=j+1;
				}
				break;
			}else{
				index-=Node[j].length;
			}
		}
	}
	printf("%d",ans);
	return 0;
} 

7-2 AC：

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
struct node{
	int weight,index1;
};
struct node2{
	int size;
	int index2;
};
bool cmp(const node a,const node b){
	return a.weight<b.weight;
}
bool cmp2(const node2 a,const node2 b){
	return a.size<b.size;
}
unordered_map<int,int> m;
int N;
vector<node2> hat;
vector<node> p;
vector<int> v;
int main(){
	cin>>N;
	hat.resize(N);
	p.resize(N);
	v.resize(N); 
	for(int i=0;i<N;i++){
		scanf("%d",&hat[i].size);
		hat[i].index2=i;
	}
	for(int i=0;i<N;i++){
		scanf("%d",&p[i].weight);
		p[i].index1=i+1;
	}
	sort(hat.begin(),hat.end(),cmp2);
	sort(p.begin(),p.end(),cmp);
	for(int i=0;i<N;i++){
		m[hat[i].index2]=p[i].index1;
	}
	for(int i=N-1;i>=0;i--){
		if(i==N-1){
			printf("%d",m[i]);
		}else{
			printf(" %d",m[i]);
		}
	}
	return 0;
} 

7-3 AC：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int G[101][101];
int inf=1000000000;
int visit[101]={0};
int cnt=0;
int N,M,ans,Max=0;
void trail(int index){
	visit[index]=1;
	cnt++;
	for(int i=1;i<=N;i++){
		if(G[index][i]==1&&visit[i]==0){
			trail(i);
			break;
		}
	}
	return;
}
int main(){
	cin>>N>>M;
	fill(G[0],G[0]+101*101,inf);
	for(int i=0;i<M;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		G[a][b]=1;
		G[b][a]=1;
	}
	for(int i=1;i<=N;i++){
		fill(visit,visit+101,0);
		cnt=0;
		trail(i);
		if(cnt>Max){
			Max=cnt;
			ans=i;
		}
	}
	printf("%d %d",ans,Max);
	return 0;
} 

7-4 AC：

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
struct node{
	int key;
	int pri;
};
int inf=1000000000;
int N,Minpri=inf,R;
vector<node> v;
vector<int> le[30];
bool cmp(const node a,const node b){
	return a.key<b.key;
}
void trail(int root,int start,int end,int level){
	le[level].push_back(root);
	int leftr,leftmin=inf,rightr,rightmin=inf;
	for(int i=start;i<root;i++){
		if(v[i].pri<leftmin){
			leftmin=v[i].pri;
			leftr=i;
		} 
	}
	for(int i=root+1;i<=end;i++){
		if(v[i].pri<rightmin){
			rightmin=v[i].pri;
			rightr=i;
		} 
	}
	if(leftmin!=inf) trail(leftr,start,root-1,level+1);
	if(rightmin!=inf) trail(rightr,root+1,end,level+1);
}

int main(){
	cin>>N;
	v.resize(N);
	for(int i=0;i<N;i++){
		scanf("%d %d",&v[i].key,&v[i].pri);
	}
	sort(v.begin(),v.end(),cmp);
	for(int i=0;i<N;i++){
		if(v[i].pri<Minpri){
			Minpri=v[i].pri;
			R=i;
		}
	}
	trail(R,0,N-1,0);
	for(int i=0;i<N;i++){
		if(le[i].size()!=0){
			for(auto it=le[i].begin();it!=le[i].end();it++){
				if(i==0&&it==le[i].begin()){
					printf("%d",v[*it].key);
				}else{
					printf(" %d",v[*it].key);
				}
			}
		}
	}
	printf("\n");
	for(int i=0;i<N;i++){
		if(le[i].size()!=0){
			for(auto it=le[i].begin();it!=le[i].end();it++){
				if(i==0&&it==le[i].begin()){
					printf("%d",v[*it].pri);
				}else{
					printf(" %d",v[*it].pri);
				}
			}
		}else{
			break;
		}
	}
	return 0;
} 

如果对你有帮助的话，记得给个赞或者关注噢，非常感谢！！！

最后祝大家都能有所收获，考到自己理想的成绩！