我是靠谱客的博主 哭泣猎豹，这篇文章主要介绍Codeforces Round #482 (Div. 2)A - Pizza, Pizza, Pizza!!!B - Treasure HuntC - Kuro and Walking Route，现在分享给大家，希望可以做个参考。
感觉最近状态不是很好，或许是得知了太多事情了，会是新的开始吧，谁知道这条路会通向什么方向呢，眼前的当务之急就是立刻找回状态，迎接即将到来的省赛
A - Pizza, Pizza, Pizza!!!
思路：看似大水题，实则大坑，将一个蛋糕均分成n份，问最少需要几刀
很明显，根据蛋糕的对称性，当n为奇数时，需要切n刀才可
而当n为偶数时，只需要切n/2刀
然而，坑点出现了，如果n为1呢，将一个蛋糕分给一个人吃，显然不需要切啊，然而做题太快完全忽略了这一点
复制代码
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#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cstring> #include <map> #include <cmath> #include <string> #include <queue> #include <stack> using namespace std; const int maxn = 1e5+10; int main() { long long n; while(scanf("%I64d",&n)!=EOF) { n++; if(n==1LL) { n=0LL; } if(n%2LL==0LL) { n /= 2LL; } printf("%I64dn",n); } return 0; }
B - Treasure Hunt
思路：这题看似恐怖，像一个大型字符串题，再看一眼数据范围，像是个O（nlog（n））的算法题
然而不难发现，这题其实最优结果一定能用字母表示，于是一切都变得简单了
最后，又是特殊值的处理，一定要警惕了，提交前一定要深思熟虑
这题的其实特殊情况只有一种，那就是当串中所有元素都相同且只有一次操作机会时，是无法达到最大值的
其余情况，只要操作足够，肯定能通过各种玄学操作达到最大值，毕竟人足够聪明
复制代码
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#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cstring> #include <map> #include <cmath> #include <string> #include <queue> #include <stack> using namespace std; const int maxn = 1e5+10; int ku[52],sh[52],ka[52]; int main() { int n; ios::sync_with_stdio(false); //freopen("in.txt","r",stdin); while(cin >> n) { memset(ku,0,sizeof ku); memset(sh,0,sizeof sh); memset(ka,0,sizeof ka); string Kuro,Shiro,Katie; cin >> Kuro >> Shiro >> Katie; int len = Kuro.size(); for(int i=0;i<len;i++) { int pos = Kuro[i]; if(pos>='a'&&pos <= 'z') { ku[pos-'a']++; } else { ku[pos-'A'+26]++; } pos = Shiro[i]; if(pos>='a'&&pos <= 'z') { sh[pos-'a']++; } else { sh[pos-'A'+26]++; } pos = Katie[i]; if(pos>='a'&&pos <= 'z') { ka[pos-'a']++; } else { ka[pos-'A'+26]++; } } int kulen=0,shlen=0,kalen=0; for(int i=0;i<52;i++) { if(ku[i]>kulen) { kulen = ku[i]; } if(sh[i]>shlen) { shlen = sh[i]; } if(ka[i]>kalen) { kalen = ka[i]; } } //cout << kulen << "*" << shlen << "*" << kalen << "*" << len << "*" << n << endl; //int lef; //cout << kulen << "**" << endl; if(kulen == len&&n==1) { kulen--; } else { kulen += n; if(kulen >len) { kulen = len; /*lef = len - kulen; if(lef%2>0) { kulen--; }*/ } } if(shlen == len&&n==1) { shlen--; } else { shlen += n; if(shlen >len) { shlen = len; /*lef = len - shlen; if(lef%2>0) { shlen--; }*/ } } if(kalen == len&&n==1) { kalen--; } else { kalen += n; if(kalen >len) { kalen = len; /*lef = len - kalen; if(lef%2>0) { kalen--; }*/ } } if(kulen>shlen&&kulen>kalen) { cout << "Kuron"; } else if(shlen>kulen&&shlen>kalen) { cout << "Shiron"; } else if(kalen>kulen&&kalen>shlen) { cout << "Katien"; } else { cout << "Drawn"; } //cout << kulen << "*" << shlen << "*" << kalen << endl << endl; } return 0; }
C - Kuro and Walking Route
思路：这一题看起来也挺吓人的，第一眼觉得可能是最小生成树
又感觉会是最短路dijkstra的一种变体
最终发现，其实也没这么复杂，因为总情况必定为n*（n-1），那么只需要dfs找出连接两个节点的路径，然后统计位于两头的城市数量xnum和ynum
那么结果即为n*（n-1） - xnum*ynum
然而，最后的小bug出现了
位于两边的城市不一定与两个节点直接相连啊，这也是一个dfs的过程，感觉之前似乎犯过这种错误
复制代码
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#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cstring> #include <map> #include <cmath> #include <string> #include <queue> #include <stack> using namespace std; const int maxn = 3e5+10; vector <int> ne[maxn]; bool vis[maxn]; int nep[maxn]; void dfs(int p,int q) { int len = ne[p].size(); vis[p] = true; for(int i=0;i<len;i++) { int nowpos = ne[p][i]; if(vis[nowpos]) { continue; } nep[nowpos] = p; if(nowpos == q) { return ; } dfs(nowpos,q); } return ; } void dfsnum(int k,long long &num) { vis[k] = true; int len = ne[k].size(); for(int i=0;i<len;i++) { int nowpos = ne[k][i]; if(vis[nowpos]) { continue; } num++; dfsnum(nowpos,num); } return ; } int main() { int n,x,y; //freopen("in.txt","r",stdin); while(scanf("%d%d%d",&n,&x,&y)!=EOF) { for(int i=1;i<=n;i++) { ne[i].clear(); } memset(vis,false,sizeof vis); //memset(len,0,sizeof len); memset(nep,-1,sizeof nep); for(int i=1;i<n;i++) { int p,q; scanf("%d%d",&p,&q); ne[p].push_back(q); ne[q].push_back(p); } if(n==1) { printf("0n"); } else { dfs(x,y); int nepy = nep[y]; int nepx; for(nepx=y;nep[nepx]!=x;nepx=nep[nepx]); long long re = (long long)(n) * (long long)(n-1); long long xnum = 1; long long ynum = 1; int xlen = ne[x].size(); int ylen = ne[y].size(); memset(vis,false,sizeof vis); for(int i=0;i<xlen;i++) { int nowpos = ne[x][i]; if(nowpos == y || nowpos == nepx) { continue; } xnum++; vis[x] = true; dfsnum(nowpos,xnum); } for(int i=0;i<ylen;i++) { int nowpos = ne[y][i]; if(nowpos == x || nowpos == nepy) { continue; } ynum++; vis[y] = true; dfsnum(nowpos,ynum); } re -= xnum * ynum; printf("%I64dn",re); //cout << xnum << "*" << ynum << endl; } } return 0; }
最后
以上就是哭泣猎豹最近收集整理的关于Codeforces Round #482 (Div. 2)A - Pizza, Pizza, Pizza!!!B - Treasure HuntC - Kuro and Walking Route的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复