数据结构与算法训练：第二十四弹

1.知识点总结

耗时：2h06min

得分：100/100

PAT知识点：字符串处理、简单贪心、基于stack的中序遍历树的结构还原、最短路径和DFS

2. 分题题解

2.1 1084 Broken Keyboard

统计type_in在type_out中未出现的字符。

简单的字符处理。

#include
using namespace std;
string type_in,type_out;
vector<bool>isExist(36,false);
string ans="";
int getId(char a){
	if(a<='z'&&a>='a'){
		return a-'a';
	}else if(a<='Z'&&a>='A'){
		return a-'A';
	}else if(a<='9'&&a>='0'){
		return a-'0'+26;
	}else{
		return 36;
	}
}
int main(){
	cin>>type_in>>type_out;
	for(int i=0;i<type_out.length();i++){
		int id=getId(type_out[i]);
		isExist[id]=true;
	}
	for(int i=0;i<type_in.length();i++){
		int id=getId(type_in[i]);
		if(!isExist[id]){
			if(id<26){
				ans+=('A'+id);
			}else{
				ans+=type_in[i];
			}
			isExist[id]=true;
		}
	}
	printf("%s",ans.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

2.2 1085 Perfect Sequence

两层循环，简单贪心。

由题意知道如果想要得到最长的序列，需要m尽可能小而M尽可能大，排序后利用双层遍历很容易可以得到答案，但是对于每次ans的更新后，需要在每层循环设置条件，当前循环肯定无法超过ans时需要即使break.同时对于相同的元素，统计完一次后需要跳过，否则会喜提超时。

#include
using namespace std;
int N,p;
typedef long long ll;
vector<ll>v;
int ans=1;
int main(){
	scanf("%d%d",&N,&p);
	v.resize(N);
	for(int i=0;i<N;i++){
		scanf("%lld",&v[i]);
	}
	sort(v.begin(),v.end());
	for(int i=0;i<N-1;i++){
		if(i&&v[i]==v[i-1])continue;
		if(N-i<ans)break;
		for(int j=N-1;j>=i;j--){
			if(j-i+1<=ans){
				break;
			}
			if(v[i]*p>=v[j]){
				ans=j-i+1;
			}
		}
	}
	printf("%d",ans);
	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

2.3 1086 Tree Traversals Again

这题虽然侥幸写出来了，但是其实卡了半小时……没遇到过的树的题型

难点：如何根据stack操作还原树的结构

思路：

• 对于Push我们认为是中序遍历中查找下一个可以插入节点位置的操作：
  • 如果是根节点，肯定就插在根节点啦
  • 如果不是的话，先看左节点有没有位置，有的话插入左节点，否则插入右节点
• 对于pop我们认为是回退定位当前的root位置的操作：
  • 如果当前节点未访问过，则标记上访问
  • 如果当前节点访问过了，则查找父节点是否被访问过，没有的话则访问到父节点同时标记上访问标记
  • 如果父节点被访问过，按照中序遍历顺序，查看右节点是否访问过，没有的话则访问到右节点同时标记上访问标记
  • 上述都不满足的话，则需要回溯找最近未访问过的父节点同时标记上访问标记

#include
using namespace std;
int N,val,root=-1;
int sroot;
string str;
//3 2 4 1 6 5
struct Node{
	int parent=-1;
	int left=-1;
	int right=-1;
};
vector<Node>nodes; 
vector<bool>vis;
bool flag=false;
void postTravel(int root){
	if(root==-1){
		return;
	}else{
		postTravel(nodes[root].left);
		postTravel(nodes[root].right);
		if(!flag){
			flag=true;
		}else{
			printf(" ");
		}
		printf("%d",root);
	}
}
int main(){
	scanf("%d",&N);
	getchar();
	nodes.resize(N+1); 
	vis.resize(N+1,false);
	for(int i=0;i<2*N;i++){
		//cout<<"当前节点"<
		getline(cin,str);
		if(str[1]=='u'){//Push 
			sscanf(str.c_str(),"Push %d",&val);
			if(root==-1){
				root=val;
				sroot=val;
			}else{
				if(nodes[root].left==-1){
					nodes[root].left=val;
				}else if(nodes[root].right==-1){
					nodes[root].right=val;
				}
				nodes[val].parent=root;
				root=val;
			}
		}else{//Pop 
			if(!vis[root]){
				vis[root]=true;
			}else{
				if(nodes[root].parent!=-1&&!vis[nodes[root].parent]){
					root=nodes[root].parent;
				}else if(nodes[root].right!=-1&&!vis[nodes[root].right]){
					root=nodes[root].right;
				}else{
					while(root!=-1&&vis[root]){
						root=nodes[root].parent;
					}
				}
				vis[root]=true;
			}
		}
	}
	postTravel(sroot);
	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

最后参考资料那边附上柳神的代码，我还没来得及看，但是思路上我们似乎是不同的，保险起见推荐柳神的~

2.4 1087 All Roads Lead to Rome

首先利用Dij算法求出最短cost的大小以及可能的候选路径pre,利用dfs搜索pre中符合题意的最优路径。

属于PAT经典压轴的题目了。

唯一需要注意的是题干中给的节点是str类型，需要用map转换成常见的int类型。

#include
using namespace std;
const int inf=INT_MAX;
map<int,string>id2name;
map<string,int>name2id;
vector<int>happy;
vector<vector<int> >cost,pre;
vector<int>temp,path;
int N,K,c,st_id,ed_id;
string st,name,name1,name2,ed="ROM";
//答案 
int total=0;
int min_cost;
int max_happy_sum=0;
int max_happy_avg=0;
void dfs(int pos,vector<int>temp){
	//pos 当前位置 开心总数 当前路径
	temp.push_back(pos);
	if(pos==st_id){
		total+=1;
		int len=temp.size();
		int temp_happy_sum=0;
		for(int i=0;i<len;i++){
			temp_happy_sum+=happy[temp[i]];
		}
		if(temp_happy_sum>max_happy_sum){
			max_happy_sum=temp_happy_sum;
			max_happy_avg=max_happy_sum/(len-1);
			path=temp;
		}else if(temp_happy_sum==max_happy_sum){
			if(max_happy_sum/(len-1)>max_happy_avg){
				max_happy_avg=max_happy_sum/(len-1);
				path=temp;
			}
		}
	}else{
		for(int i=0;i<pre[pos].size();i++){
			dfs(pre[pos][i],temp);
		}
	}
	temp.pop_back();
}
void Dij(int st,int ed){
	vector<bool>vis(N,false);
	vector<int>dis(N,inf);
	dis[st]=0;
	while(1){
		int u=-1;
		int min_dis=inf;
		for(int i=0;i<N;i++){
			if(!vis[i]&&dis[i]<min_dis){
				min_dis=dis[i];
				u=i;
			}
		}
		if(u==-1){
			break;
		}
		vis[u]=true;
		for(int v=0;v<N;v++){
			if(cost[u][v]!=inf){
				if(dis[v]>dis[u]+cost[u][v]){
					dis[v]=dis[u]+cost[u][v];
					pre[v].clear();
					pre[v].push_back(u);
				}else if(dis[v]==dis[u]+cost[u][v]){
					pre[v].push_back(u);
				}
			}
		}
	}
	min_cost=dis[ed];
	dfs(ed_id,temp);
}
int main(){
	cin>>N>>K>>st;
	happy.resize(N);
	cost.resize(N);
	pre.resize(N);
	for(int i=0;i<N;i++){
		cost[i].resize(N);
		fill(cost[i].begin(),cost[i].end(),inf);
	}
	happy[0]=0;
	name2id[st]=0;
	id2name[0]=st;
	for(int i=1;i<N;i++){
		cin>>name>>happy[i];
		name2id[name]=i;
		id2name[i]=name;
	}
	for(int i=0;i<K;i++){
		cin>>name1>>name2>>c;
		int u=name2id[name1];
		int v=name2id[name2];
		cost[u][v]=c;
		cost[v][u]=c;
	}
	st_id=name2id[st],ed_id=name2id[ed];
	Dij(st_id,ed_id);
	printf("%d %d %d %d\n",total,min_cost,max_happy_sum,max_happy_avg);
	int len=path.size();
	for(int i=len-1;i>=0;i--){
		if(i!=len-1){
			printf("->");
		}
		printf("%s",id2name[path[i]].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
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

3. 参考资料

1086. Tree Traversals Again (25)-PAT甲级真题_柳婼的博客-CSDN博客