比赛链接：https://codeforces.com/contest/1333
比赛的时候，写D的时候用了cin,cout的优化结果还是被卡了，看来cin，cout得少用。
A - Little Artem
给你n * m的矩阵，只有B和W，相邻有其他不一样的点成为好点，让好点B的数量多于W。那么直接让左上角的一块为B其余为W即可。
1 #include <iostream> 2 #include <cstdio> 3 #include <bits/stdc++.h> 4 using namespace std; 5 6 const int N = 1e5 + 10; 7 8 int n, m; 9 int T; 10 11 int main() 12 { 13 cin >> T; 14 while(T --) 15 { 16 scanf("%d%d", &n, &m); 17 for (int i = 1; i <= n; i ++) 18 { 19 20 for (int j = 1; j <= m; j ++) 21 { 22 if(i == 1 && j == 1) 23 { 24 cout << "W"; 25 } 26 else 27 cout << "B"; 28 } 29 cout << endl; 30 } 31 } 32 }
B - Kind Anton
给定一个n，长度为n的a数组和b数组，a[i]∈{1, -1, 0}，m为任意整数，a[i]只能+a[j](j < i)，那么根据题意，从后向前模拟即可。
1 #include <iostream> 2 #include <cstdio> 3 #include <bits/stdc++.h> 4 using namespace std; 5 6 const int N = 1e5 + 10; 7 8 int n, m; 9 int T; 10 int a[N]; 11 int b[N]; 12 map<int, int>s; 13 14 int main() 15 { 16 cin >> T; 17 while(T --) 18 { 19 s.clear(); 20 scanf("%d", &n); 21 for (int i = 1; i <= n; i ++) 22 scanf("%d", &a[i]), s[a[i]]++; 23 for (int i = 1; i <= n; i ++) 24 scanf("%d", &b[i]); 25 bool flag = true, flag2 = false; 26 bool t1 = false; 27 bool t2 = false; 28 for (int i = n; i >= 1; i --) 29 { 30 s[a[i]] --; 31 if(a[i] == b[i]) continue; 32 if(a[i] < b[i]) 33 { 34 if(!s[1]) 35 { 36 flag = false; 37 break; 38 } 39 } 40 if(a[i] > b[i]) 41 { 42 if(!s[-1]) 43 { 44 flag = false; 45 break; 46 } 47 } 48 } 49 if(flag) 50 { 51 puts("YES"); 52 } 53 else 54 { 55 puts("NO"); 56 } 57 } 58 59 }
C - Eugene and an array
给定长度为n的序列，定义序列a为“好的”，当且仅当，a的子段中不存在sum值为0。那么根据题意，若sum[a[i]]在i前面存在，那么这样的序列只能最后一次取到sum[a[i]]的下标k以后，数量为i - k。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N = 2e5+10; 5 ll a[N]; 6 map<ll, ll>mp; 7 int main() 8 { 9 ll n; 10 scanf("%lld", &n); 11 for(int i = 1; i <= n; i++) 12 scanf("%lld", &a[i]); 13 ll sum = 0, res = 0, last = 0; 14 mp[0] = 1; 15 for(int i = 1; i <= n; i++) 16 { 17 sum += a[i]; 18 if(mp[sum]) last = max(last, mp[sum]); 19 res += i - last; 20 mp[sum] = i+1; 21 22 } 23 printf("%lld ", res); 24 }
D - Challenges in school №41
有一个n个箭头箭头序列，只能是L（左箭头）或者R（右箭头），每次操作可以选一对相邻的相对的箭头变成相背的箭头。每秒操作至少1次，求能够恰好k秒把整个箭头序列变成没有任何相对的箭头。
那么最后的序列肯定是LLLL...LLRRR....R这样，那么可以暴力算出每一轮能移多少并且至少移几轮。因为n只有3000，最坏情况下o(n²),满足条件。
当出现RL的时候就把R的下标保存。当RLL的时候要移俩轮，所以每次有RL存在，i++。
那么假设算出x轮，一共需要移y次。那么存在有解的情况的一定是x <= k && k <= y的。然后去贪心分配轮的次数，实现具体看代码。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N = 3e3+10; 5 char s[N]; 6 int n, k; 7 vector<int>a[N]; 8 9 int main() 10 { 11 scanf("%d%d", &n, &k); 12 scanf("%s", s + 1); 13 int cnt = 0; 14 while(1) 15 { 16 cnt ++; 17 bool flag = true; 18 for (int i = 1; i < n; i ++) 19 { 20 if(s[i] == 'R' && s[i + 1] == 'L') 21 { 22 flag = false; 23 a[cnt].push_back(i); 24 swap(s[i], s[i + 1]); 25 i ++; 26 } 27 } 28 if(flag) 29 { 30 break; 31 } 32 } 33 cnt --; 34 if(cnt == 0) 35 { 36 puts("-1"); 37 return 0; 38 } 39 ll res = 0; 40 for (int i = 1; i <= cnt; i ++) 41 { 42 res += a[i].size(); 43 } 44 if(res < k || cnt > k) 45 { 46 puts("-1"); 47 return 0; 48 } 49 ll tmp = k - cnt; 50 for (int i = 1; i <= n; i ++) 51 { 52 int t = a[i].size(); 53 if(tmp >= t - 1) 54 { 55 for (int j = 0; j < t; j ++) 56 { 57 printf("1 %d ", a[i][j]); 58 } 59 tmp -= t - 1; 60 } 61 else 62 { 63 if(tmp) 64 { 65 for (int j = 0; j < tmp; j ++) 66 { 67 printf("1 %d ", a[i][j]); 68 69 } 70 printf("%d ", t - tmp); 71 for (int j = tmp; j < t; j ++) 72 { 73 printf("%d ", a[i][j]); 74 } 75 puts(""); 76 tmp = 0; 77 } 78 else 79 { 80 81 82 printf("%d ", t); 83 for (int j = 0; j <t; j ++) 84 { 85 printf("%d ", a[i][j]); 86 } 87 puts(""); 88 89 } 90 } 91 } 92 }
E - Road to 1600
定义车和皇后都从1出发每次到可以到达的最小的位置，如果无法通行，则花费1到未到达的最小位置。给定一个n找到皇后的花费比车多的n * n的矩阵。
首先1和2肯定不行，然后写个暴力程序，发现n = 3的时候就有满足的情况。再考虑n变大以后，因为车和皇后的x轴y轴的方向是一样的，所以可以让其路径相同，直到最后一个3 * 3矩阵，让皇后的花费多余车。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int n; 6 int ma[510][510]; 7 8 int main() 9 { 10 scanf("%d", &n); 11 if(n <= 2) 12 { 13 puts("-1"); 14 return 0; 15 } 16 int tmp = 0; 17 if(n == 3) 18 { 19 ma[n - 1][n - 1] = ++ tmp; 20 ma[n - 1][n] = ++ tmp; 21 ma[n][n] = ++ tmp; 22 ma[n][n - 2] = ++ tmp; 23 ma[n - 1][n - 2] = ++ tmp; 24 ma[n - 2][n] = ++ tmp; 25 ma[n - 2][n - 1] = ++ tmp; 26 ma[n - 2][n - 2] = ++ tmp; 27 ma[n][n - 1] = ++ tmp; 28 } 29 else 30 { 31 if(n % 2) 32 { 33 for (int i = 1; i <= n - 3; i ++) 34 { 35 if(i % 2) 36 { 37 for (int j = 1; j <= n; j ++) 38 { 39 ma[i][j] = ++ tmp; 40 } 41 } 42 else 43 { 44 for (int j = n; j >= 1; j --) 45 ma[i][j] = ++ tmp; 46 } 47 } 48 for (int i = 1; i <= n - 4; i ++) 49 { 50 if(i % 2) 51 { 52 for (int j = n - 2; j <= n; j ++) 53 { 54 ma[j][i] = ++ tmp; 55 } 56 } 57 else 58 { 59 for (int j = n; j >= n - 2; j --) 60 { 61 ma[j][i] = ++ tmp; 62 } 63 } 64 } 65 ma[n][n - 3] = ++ tmp; 66 ma[n - 2][n - 3] = ++ tmp; 67 ma[n - 1][n - 3] = ++ tmp; 68 } 69 else 70 { 71 72 for (int i = 1; i <= n - 3; i ++) 73 { 74 if((i % 2) != 1) 75 { 76 for (int j = 1; j <= n; j ++) 77 { 78 ma[i][j] = ++ tmp; 79 } 80 } 81 else 82 { 83 for (int j = n; j >= 1; j --) 84 ma[i][j] = ++ tmp; 85 } 86 } 87 for (int i = 1; i <= n - 4; i ++) 88 { 89 if(i % 2 != 1) 90 { 91 for (int j = n - 2; j <= n; j ++) 92 { 93 ma[j][i] = ++ tmp; 94 } 95 } 96 else 97 { 98 for (int j = n; j >= n - 2; j --) 99 { 100 ma[j][i] = ++ tmp; 101 } 102 } 103 } 104 ma[n - 2][n - 3] = ++ tmp; 105 ma[n][n - 3] = ++ tmp; 106 ma[n - 1][n - 3] = ++ tmp; 107 } 108 ma[n - 1][n - 1] = ++ tmp; 109 ma[n - 1][n] = ++ tmp; 110 ma[n][n] = ++ tmp; 111 ma[n][n - 2] = ++ tmp; 112 ma[n - 1][n - 2] = ++ tmp; 113 ma[n - 2][n] = ++ tmp; 114 ma[n - 2][n - 1] = ++ tmp; 115 ma[n - 2][n - 2] = ++ tmp; 116 ma[n][n - 1] = ++ tmp; 117 } 118 for (int i = 1; i <= n; i ++) 119 { 120 for (int j = 1; j <= n; j ++) 121 { 122 printf("%d ", ma[i][j]); 123 } 124 puts(""); 125 } 126 }
F - Kate and imperfection
给[1,n]的连续自然数。对[2,n]的每个k，都枚举所有大小恰好为k的子集，然后定义一个值为f，其遍历集合中所有的二元组，求出二元组的gcd，然后取这些gcd里面的最大值，求f的最小值。
第一眼看到这个东西的时候一点思路都没有，后来看了大佬们的思路，发现是真的很神奇，对于每一个数（无论质数合数）x，都有一个最小质因子*一个数，那么我们就贪心，给n个数排序，肯定是让最小质因子慢慢增大（1，1， 1， 2, 2，...3,），才会让f的最大值最小。
那么根据欧拉筛每个合子都是被其最小质因子筛的。就可以在o(n) + o(nlogn)的情况下得到答案。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<vector> 8 #include<set> 9 10 using namespace std; 11 12 int read() 13 { 14 char c; 15 while (c = getchar(), c != '-' && (c < '0' || c > '9')); 16 bool flag = (c == '-'); 17 if (flag) 18 c = getchar(); 19 int x = 0; 20 while (c >= '0' && c <= '9') { 21 x = x * 10 + c - '0'; 22 c = getchar(); 23 } 24 return flag ? -x : x; 25 } 26 27 const int MAXN = 500000; 28 29 bool flag[MAXN + 1]; 30 int prime[MAXN], x[MAXN + 1]; 31 32 33 int main() { 34 int n = read(); 35 int total = 0; 36 x[1] = 1; 37 for (int i = 2; i <= n; i++) 38 { 39 if (!flag[i]) 40 { 41 prime[total++] = i; 42 x[i] = 1; 43 } 44 for (int j = 0; j < total && i * prime[j] <= n; j++) { 45 int k = i * prime[j]; 46 flag[k] = true; 47 x[k] = i; 48 if (!(i % prime[j])) 49 break; 50 } 51 } 52 sort(x + 1, x + (n + 1)); 53 for (int i = 2; i <= n; i++) 54 printf("%d%c", x[i], (i == n) ? ' ' : ' '); 55 return 0; 56 }