# CF Round #575 Div3
## A. Three Piles of Candies
题意：Alice 和 Bob 两个人分糖果， 给你三堆糖果， 每人选择一堆， 剩下一堆分配使得两人的糖果数量一样多， 问两人最后糖果数最多可能是多少
思路：两个人选择糖果数少的两堆， 分最多的那一堆，最后两人最多可能分到的就是三堆糖果总数的一半
// // Created by mile on 2019/7/24. // #include <bits/stdc++.h> #define maxn 10005 #define ps push #define pb push_back using namespace std; typedef long long LL; int main() { int q; cin>>q; while(q--) { LL a, b, c; cin>>a>>b>>c; cout<<(a+b+c)/2<<endl; } return 0; }
## B Odd Sum Segments
题意：给定一个长度为n的数组和一个数字k，将数组截成k个子数组，要求每个子数组的和为奇数。
如果可以输出"YES"，以及每一个子数组的最后一个数在原数组的下标，否则输出"NO"。
思路：两数相加满足：奇数 + 奇数 = 偶数， 奇数 + 偶数 = 奇数， 偶数 + 偶数 = 偶数， 那么题目所说的子数组至少有一个奇数且奇数的个数为奇数。
得出结论： 1. 原数组中奇数小于k无答案 2.在前k-1个奇数后分割数组，前k-1个子数组中只有一个奇数，sum必为奇数，检查最后一个子数组的sum， 如果为奇数就存在答案，否则无答案。
// // Created by mile on 2019/7/24. // #include <bits/stdc++.h> using namespace std; long long num[200005], id[200005]; int main() { int q; scanf("%d", &q); while(q--) { int n, k; scanf("%d%d", &n, &k); int s = 0; for(int i = 1; i <= n; i++) { scanf("%lld", &num[i]); if(num[i]%2 == 1) s++; } if(s < k) puts("NO"); else { int cnt = 1; long long sum = 0; for(int i = 1; i<= n; i++) { sum += num[i]; if(sum%2 == 1 && k > 1) id[cnt++] = i, k--, sum = 0; } sum = 0; for(int i = id[cnt-1]+1; i <= n; i++) sum += num[i]; if(sum % 2 == 1) { puts("YES"); id[cnt] = n; for(int i = 1; i <= cnt; i++) { printf("%d ", id[i]); } puts(""); } else { puts("NO"); } } } return 0; }
## C Robot Breakout
题意：在一个x-y坐标系上有n个robots，坐标(xi, yi)，每个robot有四个功能，分别为向左，向上，向右，向下移动，但是有的robot这四个功能里面某几种坏了，为你能够找到一个坐标使得每个robot都可以达到
思路：对于完好的robot可以到达任意一点， 可以忽略。对于某个功能坏掉的robot可以得到最终坐标的一个限制，例如一个向左功能坏掉的robot，它的x坐标就是最终答案x在最小值的一个限制，因为它无法达到更左端的位置，因此对根据每个robot的坏掉的功能不断更新最终答案x和y的范围，如果得到最终minx>maxx || miny>maxy, 说明没有答案， 否则输出范围内任一点即可。
// // Created by mile on 2019/7/24. // #include <bits/stdc++.h> using namespace std; int main() { int q; scanf("%d", &q); while(q--) { int x1 = -100000, y1 = -100000; int x2= 100000, y2 = 100000; int n; scanf("%d", &n); for(int i = 1; i <= n; i++) { int x, y, a, b, c, d; scanf("%d%d%d%d%d%d", &x, &y, &a, &b, &c, &d); if(a == 0) x1 = max(x1, x); if(b == 0) y2 = min(y2, y); if(c == 0) x2 = min(x2, x); if(d == 0) y1 = max(y1, y); } if(x1 <= x2 && y1 <= y2) { printf("1 %d %d ", x1, y1); } else puts("0"); } return 0; }
## D1. RGB Substring(easy version)
题意：给定一个长度为n的由R、G、B三个字母组成的字符串，找到一个长度为k的区间，使得这个区间的字符串是"RGBRGBRGBRGBRGB...."这个无限字符串的一个子串，你可以修改任一个字母变成其他两个字母，来制造出题目要求的区间，问最少修改几个字母可以达到要求。多组测试
思路：1.暴力模拟
2.我们假设将整个字符串都变为合法字符串，利用前缀和思想，记录一个数组S， si表示要将i之前的字符串变为合法需要修改几个字母，然后对于每个i>k时，s[i]-s[i-k]就是将i-k到i这段长度为k的字符串变为合法的最小改变次数。除此之外，将整个字符串变为合法有三种情况，分别是"RGBRGB...","GBRGBRGB...","BRGBRGB..."，对每种情况分别统计一次即可。
1 // 2 // Created by mile on 2019/7/24. 3 // 4 5 #include <bits/stdc++.h> 6 7 using namespace std; 8 9 int q, n, k; 10 char str[] = "RGB"; 11 char ch[200005]; 12 int acc[200005]; 13 14 int Get(int x) { 15 for(int i = 1; i <= n; i++) { 16 acc[i] = acc[i-1] + (str[x] != ch[i]); 17 x = (x+1)%3; 18 } 19 int res = acc[k]; 20 for(int i = k+1; i <= n; i++) { 21 res = min(res, acc[i] - acc[i-k]); 22 } 23 return res; 24 } 25 26 int main() 27 { 28 scanf("%d", &q); 29 while(q--) { 30 scanf("%d%d", &n, &k); 31 scanf("%s", ch+1); 32 int res = min(min(Get(0), Get(1)), Get(2)); 33 printf("%d ", res); 34 } 35 return 0; 36 }
## D2. RGB Substring(hard version)
题意：如D1
思路：如D1思路2
1 // 2 // Created by mile on 2019/7/24. 3 // 4 5 #include <bits/stdc++.h> 6 7 using namespace std; 8 9 int q, n, k; 10 char str[] = "RGB"; 11 char ch[200005]; 12 int acc[200005]; 13 14 int Get(int x) { 15 for(int i = 1; i <= n; i++) { 16 acc[i] = acc[i-1] + (str[x] != ch[i]); 17 x = (x+1)%3; 18 } 19 int res = acc[k]; 20 for(int i = k+1; i <= n; i++) { 21 res = min(res, acc[i] - acc[i-k]); 22 } 23 return res; 24 } 25 26 int main() 27 { 28 scanf("%d", &q); 29 while(q--) { 30 scanf("%d%d", &n, &k); 31 scanf("%s", ch+1); 32 int res = min(min(Get(0), Get(1)), Get(2)); 33 printf("%d ", res); 34 } 35 return 0; 36 }
## E Connected Component on a Chessboard
题意：给定两个数b，w，在国际象棋棋盘上，找到一个联通的区域(两个方格必须有有一条公共边才算联通),使得区域里有b个黑块和w个白块。
思路：国际象棋棋盘黑白块相间分布，b和w中大的那个不能大于小的那个三倍加一，先根据白块和黑块中少的那个选择一排，首先多的可以放在少的后面一个， 然后可以放在少的上一排相同位置，最后是少的第一块前面和下一排的相同位置。初始位置可以任选，棋盘范围很大，1到1e9-1e5之间都可以。
1 // 2 // Created by mile on 2019/7/24. 3 // 4 5 #include <bits/stdc++.h> 6 7 #define pb push_back 8 #define mp make_pair 9 using namespace std; 10 11 vector<pair<int, int> > ans; 12 13 int main() 14 { 15 int q; 16 scanf("%d", &q); 17 while(q--) { 18 int b, w; 19 int x, y; 20 x = y = 1000000; 21 scanf("%d%d", &b, &w); 22 if(b < w) swap(b, w), x++; 23 for(int i = 0; i < w; i++) { 24 ans.pb(mp(x+i*2, y)); 25 if(b) { 26 ans.pb(mp(x+i*2+1, y)); 27 b--; 28 } 29 } 30 for(int i = 0; i < w; i++) { 31 if(b) { 32 ans.pb(mp(x+i*2,y+1)); b--; 33 } 34 if(b) { 35 ans.pb(mp(x+i*2, y-1)); b--; 36 } 37 } 38 if(b) ans.pb(mp(x-1, y)), b--; 39 //if(b) ans.pb(mp(x+2*w-1, y)), b--; 40 if(b != 0) { 41 puts("NO"); 42 } else { 43 puts("YES"); 44 for(auto it : ans) { 45 printf("%d %d ", it.first, it.second); 46 } 47 } 48 ans.clear(); 49 } 50 return 0; 51 }
## F K-th Path
题意：给定一个无向连通图，n个点以及m条边的长度，d(i,j)表示点i到j的最短路长度，找到所有d(i,j)中第k小的，输出其长度。
思路：k最大为400，暴力floyd，对所有边根据权值排序，计算前min(k,m)条边可以组成的最短路长度，存入数组，第k小的就是答案，由于点的数值可能很大，所以Floyd之前先对点进行离散化处理。
1 // 2 // Created by mile on 2019/7/26. 3 // 4 // 离散化点+Floyd 5 6 #include <bits/stdc++.h> 7 8 #define ps push 9 #define pb push_back 10 #define mp make_pair 11 12 using namespace std; 13 14 vector<pair<long long, pair<int, int>>> edges; 15 vector<int> ver; 16 long long dis[1005][1005]; 17 18 int main() 19 { 20 int n, m, k; 21 scanf("%d%d%d", &n, &m, &k); 22 for(int i = 1; i <= m; ++i) { 23 int u, v, w; 24 scanf("%d%d%d", &u, &v, &w); 25 edges.pb(mp(w, mp(u, v))); 26 } 27 sort(edges.begin(), edges.end()); 28 for(int i = 0; i < min(m, k); ++i) { 29 ver.pb(edges[i].second.first); 30 ver.pb(edges[i].second.second); 31 } 32 sort(ver.begin(), ver.end()); 33 ver.erase(unique(ver.begin(), ver.end()), ver.end()); 34 int sz = ver.size(); 35 memset(dis, 0x3f, sizeof(dis)); 36 for(int i = 0; i <= sz; i++) { 37 dis[i][i] = 0; 38 } 39 40 for(int i = 0; i < min(m, k); i++) { 41 int x = lower_bound(ver.begin(), ver.end(), edges[i].second.first)-ver.begin(); 42 int y = lower_bound(ver.begin(), ver.end(), edges[i].second.second)-ver.begin(); 43 dis[x][y] = dis[y][x] = min(dis[x][y], edges[i].first); 44 } 45 vector<long long> ans; 46 for(int i = 0; i < sz; i++) { 47 for(int j = 0; j < sz; j++) { 48 for(int k = 0; k < sz; k++) { 49 dis[j][k] = min(dis[j][k], dis[j][i]+dis[i][k]); 50 } 51 } 52 } 53 for(int i = 0; i < sz; i++) { 54 for(int j = i+1; j < sz; j++) { 55 ans.pb(dis[i][j]); 56 } 57 } 58 sort(ans.begin(), ans.end()); 59 printf("%lld ", ans[k-1]); 60 return 0; 61 }