1. 知识点总结

2.5h,100/100

其实还是很惊险的，因为之前做过一遍题目，所以卡在最后一题的倒数三个测试点半小时内立马找出来bug了，感觉如果没有记忆加成，本次最高也只能拿85-95这样。

2. 分题题解

2.1 PAT 1136 A Delayed Palindrome

简单的字符串+大整数加法，其实问题是简化的，大整数加法可以简化成相同长度的大整数加法。

#include
using namespace std;
string num,rnum;
string add(string a,string b){
	string ans="";
	//同样的长度
	int len=a.length();
	int s=0,c=0;
	for(int i=0;i<len;i++){
		s=c+a[len-i-1]-'0'+b[len-i-1]-'0';
		c=s/10;
		s%=10;
		ans+=to_string(s);
	} 
	while(c){
		ans+=to_string(c%10);
		c/=10;
	}
	reverse(ans.begin(),ans.end());
	printf("%s + %s = %s\n",a.c_str(),b.c_str(),ans.c_str());
	return ans;
}
bool isPalindromic(string str){
	int len=str.length();
	for(int i=0;i<len/2;i++){
		if(str[i]!=str[len-i-1]){
			return false;
		}
	}
	return true;
}
bool flag=false;
int main(){
	cin>>num;
	for(int i=1;i<=10;i++){
		if(isPalindromic(num)){
			flag=true;
			break;
		}
		rnum=num;
		reverse(rnum.begin(),rnum.end());
		num=add(num,rnum);
	}
	if(!flag){
		printf("Not found in 10 iterations.");
	}else{
		printf("%s is a palindromic number.",num.c_str());
	}
	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.2 PAT 1137 Final Grading

这题没有立刻AC，第一遍还剩最后一个测试点没有过，后来发现盲点在于对于合格的判断条件理解错误，是最终的final Grade ＞60也就是G＞60而不是Gfinal>60

英语+细心的考察

数据结构与算法分析--C语言描述_数据结构与算法_

zip 0星 超过10%的资源 38.15MB

下载

#include
using namespace std;
int P,M,N;
struct Student{
	string id;
	int Gp=-1,Gmid=-1,Gfinal=-1,G;
};
map<string,Student>mp;
vector<Student>students;
string id;int score;
bool cmp(Student a,Student b){
	if(a.G!=b.G){
		return a.G>b.G;
	}else{
		return a.id<b.id;
	}
}
int main(){
	scanf("%d%d%d",&P,&M,&N);
	for(int i=0;i<P;i++){
		cin>>id>>score;
		mp[id].id=id;
		mp[id].Gp=score;
	}
	for(int i=0;i<M;i++){
		cin>>id>>score;
		mp[id].id=id;
		mp[id].Gmid=score;
	}
	for(int i=0;i<N;i++){
		cin>>id>>score;
		mp[id].id=id;
		mp[id].Gfinal=score;
	}
	for(map<string,Student>::iterator it=mp.begin();it!=mp.end();it++){
		if((it->second).Gp<200){
			continue;//平时分未达到要求 
		}else{
			if((it->second).Gmid>(it->second).Gfinal){
				(it->second).G=(5+4*(it->second).Gmid+6*(it->second).Gfinal)/10;
			}else{
				(it->second).G=(it->second).Gfinal;
			}
			if((it->second).G<60){
				continue;//最终的总分没有及格 
			} 
			students.push_back(it->second);
		} 
	}
	sort(students.begin(),students.end(),cmp);
	for(int i=0;i<students.size();i++){
		printf("%s %d %d %d %d\n",students[i].id.c_str(),students[i].Gp,students[i].Gmid,students[i].Gfinal,students[i].G);
	}
	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

2.3 PAT 1138 Postorder Traversal

如果有看过我之前的算法复习章节，应该就知道PAT有多爱出这种二叉树了，掌握板子之后非常简单，请即将机考的读者早点背住板子，多多练习才是王道~

#include
using namespace std;
//给出pre和in输出post的第一个元素
vector<int>in,pre;
bool flag=false;
int N; 
struct Node{
	int val;
	Node*left=NULL;
	Node*right=NULL;
}; 
Node*build(int inL,int inR,int preL,int preR){
	if(inL<0||inR>=N||inL>inR||preL<0||preR>=N||preL>preR){
		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(inL,k-1,preL+1,preL+num);
	root->right=build(k+1,inR,preL+num+1,preR);
	return root;
}
void postTravel(Node*root){
	if(root!=NULL){
		postTravel(root->left);
		postTravel(root->right);
		if(!flag){
			printf("%d",root->val);
			flag=true;
		}
	}
}
int main(){
	scanf("%d",&N);
	in.resize(N);
	pre.resize(N);
	for(int i=0;i<N;i++){
		scanf("%d",&pre[i]);
	}
	for(int i=0;i<N;i++){
		scanf("%d",&in[i]);
	}
	Node*root=build(0,N-1,0,N-1);
	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

2.4 PAT 1139 First Contact

这题的难点在于最后的结果，如果有“男1-男2-男3-男4”或者“女1-女2-女3-女4”的情况，一定确保1与3以及2与4不能相同。

当然异性crush不会有上述情况~

我的题解写得不是很简洁，有多余的空间申请b2g和g2b这种

吐槽一下这个题面，陈越姥姥真爱玩儿😆

#include
using namespace std;
int N,M;
int K;
const int maxn=10000;
vector<vector<int>>b2b(maxn);//男-男 
vector<vector<int>>g2g(maxn);//女-女 
vector<vector<int>>b2g(maxn);
vector<vector<int>>g2b(maxn);
vector<vector<bool>>sb(maxn),d(maxn),sa(maxn);
int u,v;
string a,b;
struct Node{
	int a,b;
	bool operator<(Node node)const{
		if(this->a!=node.a){
			return this->a<node.a;
		}else{
			return this->b<node.b;
		}
	};
	bool operator==(Node node)const{
		return this->a==node.a&&this->b==node.b;
	};
};
int main(){
	for(int i=0;i<maxn;i++){
		sb[i].resize(maxn);
		sa[i].resize(maxn);
		d[i].resize(maxn);
		fill(sb[i].begin(),sb[i].end(),false);
		fill(sa[i].begin(),sa[i].end(),false);
		fill(d[i].begin(),d[i].end(),false);
	}
	scanf("%d%d",&N,&M);
	for(int i=0;i<M;i++){
		cin>>a>>b;
		u=abs(stoi(a));v=abs(stoi(b));
		if(a[0]=='-'){
			if(b[0]=='-'){
				g2g[u].push_back(v);
				g2g[v].push_back(u);
				sa[u][v]=true;
				sa[v][u]=true;
			}else{
				g2b[u].push_back(v);
				b2g[v].push_back(u);
				d[u][v]=true;
				d[v][u]=true;
			}
		}else{
			if(b[0]=='-'){
				b2g[u].push_back(v);
				g2b[v].push_back(u);
				d[u][v]=true;
				d[v][u]=true;
			}else{
				b2b[u].push_back(v);
				b2b[v].push_back(u);
				sb[u][v]=true;
				sb[v][u]=true;
			}
		}
	}
	scanf("%d",&K);
	for(int i=0;i<K;i++){
		cin>>a>>b;
		u=abs(stoi(a));v=abs(stoi(b));
		Node temp;
		set<Node>ans;
		if(a[0]=='-'){
			if(b[0]=='-'){
				//女-（女-女）女 
				for(int x=0;x<g2g[u].size();x++){
					for(int y=0;y<g2g[v].size();y++){
						if(sa[g2g[u][x]][g2g[v][y]]&&g2g[v][y]!=u&&g2g[u][x]!=v){
							temp.a=g2g[u][x];
							temp.b=g2g[v][y];
							ans.insert(temp);
						}
					}
				}
			}else{
				//女-（女-男）-男 
				for(int x=0;x<g2g[u].size();x++){
					for(int y=0;y<b2b[v].size();y++){
						if(d[g2g[u][x]][b2b[v][y]]){
							temp.a=g2g[u][x];
							temp.b=b2b[v][y];
							ans.insert(temp);
						}
					}
				}
			} 
		}else{
			if(b[0]=='-'){
				//男-（男-女）女 
				for(int x=0;x<b2b[u].size();x++){
					for(int y=0;y<g2g[v].size();y++){
						if(d[b2b[u][x]][g2g[v][y]]){
							temp.a=b2b[u][x];
							temp.b=g2g[v][y];
							ans.insert(temp);
						}
					}
				}
			}else{
				//男-（男-男）-男 
				for(int x=0;x<b2b[u].size();x++){
					for(int y=0;y<b2b[v].size();y++){
						if(sb[b2b[u][x]][b2b[v][y]]&&b2b[v][y]!=u&&b2b[u][x]!=v){
							temp.a=b2b[u][x];
							temp.b=b2b[v][y];
							ans.insert(temp);
						}
					}
				}
			} 
		}
		//输出答案
		int total= ans.size();
		printf("%d\n",total);
		for(set<Node>::iterator it=ans.begin();it!=ans.end();it++){
			printf("%04d %04d\n",(*it).a,(*it).b);
		} 
		
	}
	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
127
128
129

3. 参考资料