1. 知识点总结

100/100,2h10min

本次的题目涉及很多经典数据结构，但是模板用的不多，基本的暴力+STL即可解决

2. 分题题解

2.1 PAT 1132 Cut Integer

字符串处理,基础的基础哈

#include
using namespace std;
int N;
string Z;
int main(){
	scanf("%d",&N);
	while(N--){
		cin>>Z;
		int len=Z.length();
		int a=stoi(Z.substr(0,len/2));
		int b=stoi(Z.substr(len/2,len));
		if(a*b&&stoi(Z)%(a*b)==0){
			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

2.2 PAT 1133 Splitting A Linked List

链表基础题，其实简单的写法最后用merge或者insert合并可能看起来更简洁

#include
using namespace std;
//将负数单独拎出来提到前面去
struct Node{
	int addr;
	int val;
	int next=-1;
}; 
int N,K,head;
map<int,Node>mp;
Node temp;
vector<Node>a,b,c,d; //负数 小于等于K 大于等于K 
int main(){
	scanf("%d%d%d",&head,&N,&K);
	for(int i=0;i<N;i++){
		scanf("%d%d%d",&temp.addr,&temp.val,&temp.next);
		mp[temp.addr]=temp;
	}
	int p=head;
	while(p!=-1){
		temp=mp[p];
		p=temp.next;
		if(temp.val<0){
			a.push_back(temp);
		}else if(temp.val<=K){
			b.push_back(temp);
		}else{
			c.push_back(temp);
		}
	}
	//输出答案
	for(int i=0;i<a.size();i++){
		d.push_back(a[i]);
	}
	for(int i=0;i<b.size();i++){
		d.push_back(b[i]);
	}
	for(int i=0;i<c.size();i++){
		d.push_back(c[i]);
	}
	int lend=d.size();
	for(int i=0;i<lend;i++){
		printf("%05d %d ",d[i].addr,d[i].val);
		if(i+1<lend){
			printf("%05d\n",d[i+1].addr);
		}
	}
	printf("-1");
	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

2.3 PAT 1134 Vertex Cover

图论，关键是理解题目的意思：需要使得给的sets包含图中所有边涉及到的两个结点之一

#include
using namespace std;
int N,M,K,u,v,num,a;
vector<bool>has;
struct Edge{
	int u,v;
};
vector<Edge>edges;
Edge temp;
int main(){
	scanf("%d%d",&N,&M);
	for(int i=0;i<M;i++){
		scanf("%d%d",&temp.u,&temp.v);
		edges.push_back(temp);
	}
	scanf("%d",&K);
	has.resize(N);
	for(int i=0;i<K;i++){
		scanf("%d",&num);
		fill(has.begin(),has.end(),false);
		for(int j=0;j<num;j++){
			scanf("%d",&a);
			has[a]=true;
		}
		bool flag=true;
		for(int x=0;x<M;x++){
			temp=edges[x];
			
			if(has[temp.u]||has[temp.v]){
				continue;
			}else{
				printf("No\n");
				flag=false;
				break;
			}
		}
		if(flag){
			printf("Yes\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

2.4 PAT 1135 Is It A Red-Black Tree

判断涉及到重新构建树（根据in和pre数组），层次遍历（为每个叶子结点跟踪到父节点做准备）;

需要理解题意的基础上掌握一定的二叉树模板进行解题，难点在于：

(5) For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
1

的判断。

具体代码如下，自认为注释还是可以的~

#include
using namespace std;
int K,N; 
vector<int>pre,in;
struct Node{
	int val;
	Node*left=NULL;
	Node*right=NULL;
	Node*parent=NULL;
	int cnt=-1;
};
bool r1b2;
Node *build(int preL,int preR,int inL,int inR){
	if(preL<0||preR>=N||inL<0||inR>=N||preL>preR||inL>inR){
		return NULL;
	}
	Node*root=new Node;
	root->val=pre[preL];
	int k;
	for(k=inL;k<=inR;k++){
		if(in[k]==root->val){
			break;
		}
	}
	int num=k-inL;
	root->left=build(preL+1,preL+num,inL,k-1);//num 
	root->right=build(preL+num+1,preR,k+1,inR);
	if(root->val<0){
		//如果结点为红色，子节点需要为黑
		if((root->left!=NULL&&root->left->val<0)||(root->right!=NULL&&root->right->val<0)){
			r1b2=false;
		}
	}
	return root;
}
bool cmp(int a,int b){
	return abs(a)<abs(b);
}
bool isok; 
void levelTravel(Node*root){
	queue<Node*>q;
	q.push(root);
	while(!q.empty()){
		Node*top=q.front();
		q.pop();
		if(top->left!=NULL){
			top->left->parent=top;
			q.push(top->left);
		}
		if(top->right!=NULL){
			top->right->parent=top;
			q.push(top->right);
		}
		if((top->left==NULL||top->right==NULL)&&isok){
			//遍历其根结点 
			int cnt=1;			
			while(top!=NULL){
				if(top->val>0){
					cnt++;
				}
				if(top->cnt==-1){
					top->cnt=cnt;
				}else if(top->cnt!=cnt){
					isok=false;
					break;
				}
				top=top->parent;
			}
		}
	}
}

int main(){
	scanf("%d",&K);
	while(K--){
		r1b2=true;
		isok=true;
		scanf("%d",&N);
		pre.resize(N);
		for(int i=0;i<N;i++){
			scanf("%d",&pre[i]);
		}
		in=pre;
		sort(in.begin(),in.end(),cmp);
		Node*root=build(0,N-1,0,N-1);
		if(root->val<0||!r1b2){
			printf("No\n");//根节点不为黑 
		}else{
			//每个结点到其降序输出的叶子结点经过的黑色结点都相同数目 
			levelTravel(root);
			if(!isok){
				printf("No\n");
			}else{
				printf("Yes\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
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

3. 参考资料

无