1. 知识点总结

98/100耗时2h，最后一题还剩2分没有继续死磕了……哇啊。

2. 分题题解

2.1 1108 Finding Average

还记得以前第一次见到这种题目的时候，觉得很麻烦，特别是对于字符串合法性判断的地方，写多了其实还是有点手感的，代码比以前减少冗余了捏~

#include
using namespace std;
int N,cnt=0;
double num,sum=0;
string str;
bool isLegal(string str,double &num){
	int len=str.length();
	//首先判断是否是数字
	int dot_pos=-1;
	for(int i=0;i<len;i++){
		if((str[i]=='+'||str[i]=='-')&&i==0){
			continue;
		}else if(str[i]<='9'&&str[i]>='0'){
			continue;
		}else if(str[i]=='.'&&dot_pos==-1){
			dot_pos=i;
			continue;
		}else{
			return false;
		}
	} 
	if(dot_pos!=-1&&len-dot_pos-1>=3){
		return false;
	}
	num=atof(str.c_str());
	if(num<-1000||num>1000){
		return false;
	}
	return true;
}
int main(){
	scanf("%d",&N);
	getchar();
	for(int i=0;i<N;i++){
		cin>>str;
		if(isLegal(str,num)){
			sum+=num;
			cnt++;
		}else{
			printf("ERROR: %s is not a legal number\n",str.c_str());
		}
	}
	if(cnt==0){
		printf("The average of %d numbers is Undefined",cnt);
	}else if(cnt==1){
		printf("The average of %d number is %.2f",cnt,sum/cnt);
	}else{
		printf("The average of %d numbers is %.2f",cnt,sum/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
40
41
42
43
44
45
46
47
48
49
50
51

2.2 1109 Group Photo

好像也是之前卡住的题目，主要在行排序的规则的理解，因为数组开的是[0,m-1]所以第一个位置下标号应该是m/2，然后左右散开排列

#include
using namespace std;
struct Node{
	string name;
	int height;
};
int N,K,m;
vector<Node>nodes,row;
bool cmp(Node a,Node b){
	if(a.height!=b.height){
		return a.height>b.height;
	}else{
		return a.name<b.name;
	}
}
int main(){
	scanf("%d%d",&N,&K);
	nodes.resize(N);
	for(int i=0;i<N;i++){
		cin>>nodes[i].name>>nodes[i].height;
	}
	sort(nodes.begin(),nodes.end(),cmp);
	int index=0;
	for(int i=0;i<K;i++){
		if(i==0){
			m=N/K+N%K;
		}else{
			m=N/K;
		}
		row.resize(m);
		//下面开始排列位置
		int pos=m/2;
		int posl=pos-1;
		int posr=pos+1;
		row[pos]=nodes[index++];
		for(int x=0;x<m-1;x++){
			//printf("pos=%d,posl=%d,posr=%d\n",pos,posl,posr);
			if(x%2==0){
				row[posl]=nodes[index++];
				posl--;
			}else{
				row[posr]=nodes[index++];
				posr++;
			}
		}
		//输出本行结果
		for(int x=0;x<m;x++){
			if(x){
				printf(" ");
			}
			printf("%s",row[x].name.c_str());
		} 
		printf("\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

2.3 1110 Complete Binary Tree

基于数组的完全二叉树的判断，需要背住的模板。

#include
using namespace std;
struct Node{
	int val;
	int left=-1;
	int right=-1;
};
int N,ans;
vector<Node>nodes;
vector<bool>isC;
string a,b;
//判断是否是完全二叉树
bool isComplete(int root){
	queue<int>q;
	q.push(root);
	while(!q.empty()){
		int top=q.front();
		q.pop();
		if(top==-1){
			break;
		}else{
			ans=top;
		}
		q.push(nodes[top].left);
		q.push(nodes[top].right);
	}
	while(!q.empty()){
		int top=q.front();
		if(top!=-1){
			return false;
		}
		q.pop();
	}
	return true;
} 
int main(){
	scanf("%d",&N);
	nodes.resize(N);
	isC.resize(N);
	fill(isC.begin(),isC.end(),false);
	for(int i=0;i<N;i++){
		nodes[i].val=i;
		cin>>a>>b;
		if(a!="-"){
			nodes[i].left=atoi(a.c_str());
			isC[atoi(a.c_str())]=true;
		}
		if(b!="-"){
			nodes[i].right=atoi(b.c_str());
			isC[atoi(b.c_str())]=true;
		}
	}
	int root;
	for(int i=0;i<N;i++){
		if(!isC[i]){
			root=i;
			break;
		}
	}
	if(isComplete(root)){
		printf("YES %d",ans);
	}else{
		printf("NO %d",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

2.4 1111 Online Map

最短路径+DFS

求两条路径，一条是最短距离路径（距离相等时取耗时最短），一条是最短时间路径（时间相等时取经过节点最少）

emm没有订正，下面的代码错了测试点2被扣2分~看了柳神的代码，贴在后面参考资料——真的简练😍

#include
using namespace std;
//最短、最快 
const int inf=INT_MAX;
int N,M;
vector<vector<int> >t,d;//时间，距离
int u,v,one_way,len,tim,st,ed; 
//对于最短路径，如果相同，选择其中最快的
vector<vector<int> >pre;
vector<int>temp,short_path,fast_path;
int min_time=inf,min_i=inf;
void DFS_f(int id,vector<int>temp){
	temp.push_back(id);
	if(id==st){
		//计算时间 
		int temp_time=0;
		for(int i=temp.size()-1;i>=1;i--){
			temp_time+=t[temp[i]][temp[i-1]];
		}
		if(temp_time<min_time){
			min_time=temp_time;
			short_path=temp;
		}
	}else{
		for(int i=0;i<pre[id].size();i++){
			DFS_f(pre[id][i],temp);
		}
	}
	temp.pop_back();
}
void DFS_i(int id,vector<int>temp){
	temp.push_back(id);
	if(id==st){
		int cnt=temp.size();
		if(cnt<min_i){
			min_i=cnt;
			fast_path=temp;
		}
	}else{
		for(int i=0;i<pre[id].size();i++){
			DFS_i(pre[id][i],temp);
		}
	}
	temp.pop_back();
}
int findShortest(int st,int ed){
	pre.resize(N);
	vector<int>dis(N);
	vector<bool>vis(N,false);
	fill(dis.begin(),dis.end(),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;
				break;
			}
		}
		if(u==-1){
			break;
		}
		vis[u]=true;
		//更新路径
		for(int v=0;v<N;v++){
			if(dis[u]==inf){
				break;
			}
			if(d[u][v]==inf){
				continue;
			}else if(dis[v]>dis[u]+d[u][v]){
				pre[v].clear();
				pre[v].push_back(u);
				dis[v]=dis[u]+d[u][v];
			}else if(dis[v]==dis[u]+d[u][v]){
				pre[v].push_back(u);
				dis[v]=dis[u]+d[u][v];
			}
		} 
	}
	//寻找最短且最快的路径
	DFS_f(ed,temp);
	return dis[ed];
}
//对于最快路径，选择其中size最小的
int findFast(int st,int ed){
	pre.clear();
	pre.resize(N);
	vector<int>dis(N);
	vector<bool>vis(N,false);
	fill(dis.begin(),dis.end(),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;
				break;
			}
		}
		if(u==-1){
			break;
		}
		vis[u]=true;
		//更新路径
		for(int v=0;v<N;v++){
			if(dis[u]==inf){
				break;
			}
			if(t[u][v]==inf){
				continue;
			}else if(dis[v]>dis[u]+t[u][v]){
				pre[v].clear();
				pre[v].push_back(u);
				dis[v]=dis[u]+t[u][v];
			}else if(dis[v]==dis[u]+t[u][v]){
				pre[v].push_back(u);
				dis[v]=dis[u]+t[u][v];
			}
		} 
	}
	temp.clear();
	DFS_i(ed,temp);
	return dis[ed];
}
int main(){
	scanf("%d%d",&N,&M);
	t.resize(N);
	d.resize(N);
	for(int i=0;i<N;i++){
		t[i].resize(N);
		fill(t[i].begin(),t[i].end(),inf);
		d[i].resize(N);
		fill(d[i].begin(),d[i].end(),inf);
	}
	for(int i=0;i<M;i++){
		scanf("%d%d%d%d%d",&u,&v,&one_way,&len,&tim);
		t[u][v]=tim;
		d[u][v]=len;
		if(one_way==0){
			t[v][u]=tim;	
			d[v][u]=len;
		}
	}
	scanf("%d%d",&st,&ed);
	int ans1=findShortest(st,ed);
	int ans2=findFast(st,ed);
	if(short_path==fast_path){
		printf("Distance = %d; Time = %d:",ans1,ans2);
		int len1=short_path.size();
		for(int i=len1-1;i>=0;i--){
			if(i!=len1-1){
				printf("->");
			}
			printf(" %d",short_path[i]);
			if(i){
				printf(" ");
			}
		}
		printf("\n");
	}else{
		//地址 
		printf("Distance = %d:",ans1);
		int len1=short_path.size();
		for(int i=len1-1;i>=0;i--){
			if(i!=len1-1){
				printf("->");
			}
			printf(" %d",short_path[i]);
			if(i){
				printf(" ");
			}
		}
		printf("\n");
		//时间
		printf("Time = %d:",ans2);
		int len2=fast_path.size();
		for(int i=len2-1;i>=0;i--){
			if(i!=len2-1){
				printf("->");
			}
			printf(" %d",fast_path[i]);
			if(i){
				printf(" ");
			}
		}
		printf("\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
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194

3. 参考资料

1111. Online Map (30)-PAT甲级真题（Dijkstra + DFS）_柳婼的博客-CSDN博客