2022年秋季PAT线上考试总结

本来报名是为了激励一下自己去准备机试的，没错本来是想退考的……结果昂忘记提前一周取消了（超时退考不退报名费来着），就赶鸭子上架去考了
很多去考试的人主要是为了升学的原因，但现在其实z大不能用PAT抵消机试了，所以酌情报名⑧，好像杭电可以抵，具体俺也不清楚了捏~

关于报名：pat报名其实可以在牛客网拿代金券抵消一部分的费用【链接】
关于准备：在PAT官网刷完一轮甲级题库就可以上了，耗时两个月（一个月也行，如果训练密度大的话~）【链接】
关于注意事项：开考前一周会有邮件发过来，除了通知考试二维码以及准考证号等信息之外，还会有线上环境部署的链接，也可以在B站搜“OMS考试”，讲解的很详细。我当时还看了知乎的一个细节扩充版【链接】，具体硬件配置如下：

• 关于鼠标：参考知乎回答所以采用无线USB鼠标
• 关于键盘：笔记本电脑自带键盘
• 关于双机位（笔记本电脑自带前置摄像头+手机第二摄像头+手机支架即可）

考试题目总结

第一题：考察英文阅读理解，老实说一开始没读懂题目意思，也没看懂样例和Tips直接跳过，没有纠结，最后回过头发现是简单的找规律和数组，注意特殊点的判断，看到考场上很多人最后卡在特殊点的1分的
第二题：快速排序的概念流程考核（考察数组和找规律）
第三题：并查集+图论（属于模板题的变式，理论上应该不难，但是由于第一遍读题就比较马虎导致数据结构设置很冗余最后半小时也懒得去改代码逻辑了，导致最后的失分点在此题23/25😅）
第四题：前序+中序构建二叉树最后后序输出，同时判断树是完全二叉树还是完美二叉树还是去掉最后一层就是完美二叉树还是普通树，分成四类讨论输出分类编号（模板题）

代码

第一题：AC

#include
using namespace std;
int n,h;
vector<int>v;

int main(){
	scanf("%d%d",&n,&h);
	v.resize(n);
	for(int i=0;i<n;i++){
		scanf("%d",&v[i]);
	}
	int ans=v[0];
	int cnt=1;
	for(int i=0;i<n;i++){
		int st=v[i];
		int ed=v[i]+h;
		int temp_cnt=1;
		int j;
		for(j=i+1;j<n;j++){
			if(v[j]>ed){
				break;
			}
			temp_cnt++;
		}
		if(temp_cnt>cnt){
			cnt=temp_cnt;
			if(v[j-1]-h<st){
				st=v[j-1]-h;
			}
			ans=st;
		}
	}
	if(cnt==1){
		printf("%d %d",v[0]-h,cnt);
	}else{
		printf("%d %d",ans,cnt);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

第二题：AC

#include
using namespace std;
int N,M;
vector<int>v;
int main(){
	scanf("%d",&N);
	bool flag;
	while(N--){
		scanf("%d",&M);
		v.resize(M);
		for(int i=0;i<M;i++){
			scanf("%d",&v[i]);
		}	
		flag=false;
		//第二轮快排 
		vector<int>preMax(M);
		vector<int>nextMin(M);
		//首先需要找到一个数字，前面的都小于等于自己，后面的都大于等于自己
		//接着在它前面找到一个数字（前面的都小于等于自己），后面的都大于等于自己
		//接着在它后面找到一个数字（前面的都小于等于自己，后面的都大于等于自己）
		preMax[0]=v[0];
		nextMin[M-1]=v[M-1];
		for(int i=1;i<M;i++){
			if(v[i]>preMax[i-1]){
				preMax[i]=v[i];
			}else{
				preMax[i]=preMax[i-1];
			}
			if(v[M-1-i]<nextMin[M-i]){
				nextMin[M-i-1]=v[M-1-i];
			}else{
				nextMin[M-i-1]=nextMin[M-i];
			}
		} 
		//计算符合条件的指针 
		int cnt=0; 
		bool edge=false;
		for(int i=0;i<M;i++){
			if(v[i]>=preMax[i]&&v[i]<=nextMin[i]){
				cnt++;
				if(i==0||i==M-1){
					edge=true;
				}
			}
		}
		if(cnt==2&&edge){
			flag=true;
		}else if(cnt>=3){
			flag=true;
		}
		if(flag){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

第三题：23/25
就不列了，最后改得面目全非本地没有保存……但是考试取最高一次得分😌

第四题：AC

#include
using namespace std;
int N;
vector<int>in,pre;
//说明种类：1-完美二叉树 2-完全二叉树 3-pcb树 0-其他
struct Node{
	int val;
	int height=0;
	Node*left=NULL;
	Node*right=NULL;
}; 
Node*root; 
bool isCBT(Node*root){
	queue<Node*>q;
	q.push(root);
	while(!q.empty()){
		Node*top=q.front();
		q.pop();
		if(top==NULL){
			break;
		}
		q.push(top->left);
		q.push(top->right);
	}
	while(!q.empty()){
		Node*top=q.front();
		q.pop();
		if(top!=NULL){
			return false;
		}
	}
	return true;
}
int getKind(Node*root){
	//判断种类
	bool flag=isCBT(root);
	if(flag){
		for(int i=0;i<N;i++){
			int cnt=pow(2.0,i+1)-1;
			if(cnt==N){
				return 1;
			}else if(cnt>N){
				break;
			}
		}
		return 2;
	}else{
		queue<Node*>q;
		q.push(root);
		vector<int>level(N,0);
		int max_level=0;
		while(!q.empty()){
			Node*top=q.front();
			q.pop();
			//printf("level=%d val=%d\n",top->height,top->val);
			level[top->height]++;
			if(top->height>max_level){
				max_level=top->height;
			}
			if(top->left!=NULL){
				top->left->height=top->height+1;
				q.push(top->left);
			}
			if(top->right!=NULL){
				top->right->height=top->height+1;
				q.push(top->right);
			}
		}
		int num=1;
		for(int i=0;i<max_level;i++){
			if(level[i]!=num){
				return 0;
			}
			num*=2;
		}
		return 3;
	}
}
Node*build(int inL,int inR,int preL,int preR){
	if(inL<0||inR>=N||preL<0||preR>=N||inL>inR||preL>preR){
		return NULL;
	}
	Node*node=new Node;
	node->val=pre[preL];
	int k;
	for(k=inL;k<=inR;k++){
		if(in[k]==pre[preL]){
			break;
		}
	}
	int num=k-inL;
	node->left=build(inL,k-1,preL+1,preL+num);
	node->right=build(k+1,inR,preL+num+1,preR);
	return node;
}
bool flag=false;
void postTravel(Node*root){
	if(root==NULL){
		return;
	}else{
		postTravel(root->left);
		postTravel(root->right);
		if(flag){
			printf(" ");
		}else{
			flag=true;
		}
		printf("%d",root->val);
	}
}
int main(){
	scanf("%d",&N);
	pre.resize(N);
	in.resize(N);
	for(int i=0;i<N;i++){
		scanf("%d",&in[i]);
	}
	for(int i=0;i<N;i++){
		scanf("%d",&pre[i]);
	}
	root=build(0,N-1,0,N-1);
	int kind=getKind(root);
	printf("%d\n",kind);
	postTravel(root);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

考场上满分的大佬很多，我已经排到70+了🤣~
好好准备的话90+不难，但是考场上一道AC的都没有也是大有人在（实时排名系统）。所以报名之后尽量用心准备吧，毕竟花了银子哇（心疼money++），没有时间准备记得及时退考（考前一周~）