首页 > 代码库 > Codeforces Round #370 - #379 (Div. 2)
Codeforces Round #370 - #379 (Div. 2)
题意:
思路:
Codeforces Round #370
A - Memory and Crow
题意:有一个序列,然后对每一个进行ai?=?bi?-?bi?+?1?+?bi?+?2?-?bi?+?3.... 的操作,最后得到了a 序列,给定 a 序列,求原序列。
思路:水。
1 #include <set> 2 #include <map> 3 #include <stack> 4 #include <queue> 5 #include <cstdio> 6 #include <vector> 7 #include <cstring> 8 #include <iostream> 9 #include <algorithm> 10 using namespace std; 11 typedef long long LL; 12 #define mem(x,y) memset(x, y, sizeof(x)) 13 #define lson l,m,rt << 1 14 #define rson m+1,r,rt << 1 | 1 15 int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);} 16 int lcm(int a, int b){return a / gcd(a, b) * b;} 17 const int maxn = 100000 + 5; 18 int a[maxn], b[maxn]; 19 int main() 20 { 21 int n; 22 scanf("%d", &n); 23 for(int i = 1; i <= n; i++) 24 { 25 scanf("%d", &a[i]); 26 } 27 a[n + 1] = 0; 28 for(int i = 1; i <= n; i++) 29 { 30 printf("%d%c", a[i] + a[i + 1], i == n ? ‘\n‘ : ‘ ‘); 31 } 32 return 0; 33 }
B - Memory and Trident
题意:一个人站在坐标原点处,他可以往上(U), 下(D), 左(L), 右(R), 四个方向移动,现给你一个移动序列,为了使他最后仍然能回到原点,你需要对这个序列做一些改变,每次可以改变其中一个字母,问最少的改变次数.
思路:水。
1 #include <set> 2 #include <map> 3 #include <stack> 4 #include <queue> 5 #include <cstdio> 6 #include <vector> 7 #include <cstring> 8 #include <iostream> 9 #include <algorithm> 10 using namespace std; 11 typedef long long LL; 12 #define mem(x,y) memset(x, y, sizeof(x)) 13 #define lson l,m,rt << 1 14 #define rson m+1,r,rt << 1 | 1 15 int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);} 16 int lcm(int a, int b){return a / gcd(a, b) * b;} 17 18 const int maxn = 100000 + 5; 19 char s[maxn]; 20 21 int main() 22 { 23 scanf("%s", s); 24 int ok = 0, ans = 0, cnt_ud = 0, cnt_rl = 0; 25 for(int i = 0; i < strlen(s); i++) 26 { 27 switch(s[i]) 28 { 29 case ‘U‘: cnt_ud++;break; 30 case ‘D‘: cnt_ud--;break; 31 case ‘L‘: cnt_rl++;break; 32 case ‘R‘: cnt_rl--;break; 33 } 34 } 35 int temp = abs(cnt_rl) + abs(cnt_ud); 36 if(temp % 2 == 0) ok = 1, ans = temp / 2; 37 else ok = 0; 38 if(ok) 39 { 40 printf("%d\n", ans); 41 } 42 else 43 { 44 puts("-1"); 45 } 46 return 0; 47 }
C - Memory and De-Evolution
题意:给你两个值 a 和 b (a > b), 代表这里有两个等边三角形, 边长分别为 a 和 b, 你可以对边长为 a 的三角形进行变换, 每次变化你可以选择一条边, 并为其重新指定一个长度, 当然变换完成后还能组成一个三角形.问最少经过多少次变换可以把等边三角形的三边长度从 a 变换到 b
思路:倒过来想可能简单点,你每次要达到什么样的数据能最优,肯定是根据不变的两条边得到最大的第三条边。
然后特判一下这条新的第三条边大于x的情况就好了。
1 #include <set> 2 #include <map> 3 #include <stack> 4 #include <queue> 5 #include <cstdio> 6 #include <vector> 7 #include <cstring> 8 #include <iostream> 9 #include <algorithm> 10 using namespace std; 11 typedef long long LL; 12 #define mem(x,y) memset(x, y, sizeof(x)) 13 #define lson l,m,rt << 1 14 #define rson m+1,r,rt << 1 | 1 15 int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);} 16 int lcm(int a, int b){return a / gcd(a, b) * b;} 17 18 int main() 19 { 20 int x, y; 21 scanf("%d%d", &x, &y); 22 int cnt = 0; 23 int a[3]; 24 a[0] = a[1] = a[2] = y; 25 while(a[0] != x && a[1] != x && a[2] != x) 26 { 27 sort(a, a + 3); 28 a[0] = a[1] + a[2] - 1; 29 if(a[0] > x) a[0] = x; 30 cnt++; 31 } 32 printf("%d\n", cnt + 2); 33 return 0; 34 }
D - Memory and Scores
题意:A初始有一个分数a,B初始有一个分数b,有t轮比赛,每次比赛都可以取[-k, k]之间的数,问你最后A比B大的情况有多少种。
思路:
1 #include <set> 2 #include <map> 3 #include <stack> 4 #include <queue> 5 #include <cstdio> 6 #include <vector> 7 #include <cstring> 8 #include <iostream> 9 #include <algorithm> 10 using namespace std; 11 typedef long long LL; 12 #define mem(x,y) memset(x, y, sizeof(x)) 13 #define lson l,m,rt << 1 14 #define rson m+1,r,rt << 1 | 1 15 int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);} 16 int lcm(int a, int b){return a / gcd(a, b) * b;} 17 18 const int maxn = 210000; 19 const int mod = 1e9 + 7; 20 int a, b, k, t; 21 LL dp[105][maxn], sum[maxn]; 22 23 int main() 24 { 25 scanf("%d%d%d%d", &a, &b, &k, &t); 26 dp[0][0] = 1; 27 for(int i = 1; i <= t; i++) 28 { 29 for(int j = 0; j < maxn; j++) 30 { 31 if(j > 0) 32 sum[j] = dp[i - 1][j] + sum[j - 1]; 33 else 34 sum[j] = dp[i - 1][j]; 35 sum[j] %= mod;//sum来处理前缀和 36 } 37 for(int j = 0; j < maxn; j++) 38 { 39 if((j - 2 * k - 1) >= 0) 40 dp[i][j] = (sum[j] - sum[j - 2 * k - 1] + mod) % mod; 41 else 42 dp[i][j] = (sum[j] + mod) % mod; 43 } 44 } 45 46 for(int j = 0; j < maxn; j++) 47 { 48 if(j > 0) 49 sum[j] = (sum[j - 1] + dp[t][j]) % mod; 50 else 51 sum[j] = dp[t][j] % mod; 52 } 53 54 int ans = 0; 55 for(int i=0; i<=2*k*t; i++) 56 { 57 if(i + a - b - 1 >= 0) 58 ans += (LL)dp[t][i] * sum[i+a-b-1] % mod; 59 ans %= mod; 60 } 61 printf("%d\n", ans); 62 return 0; 63 }
Codeforces Round #371
A - Crazy Computer
题意:就是你一定时间内不输入新的字,它就会清屏。问你最后你屏幕上还有几个字。
思路:水。
1 #include <cstdio> 2 int main() 3 { 4 int n, c; 5 scanf("%d%d", &n, &c); 6 int x, last = 0, tot = 0; 7 for(int i = 0; i < n; i++) 8 { 9 scanf("%d", &x); 10 if(x - last > c) tot = 0; 11 last = x, tot++; 12 } 13 printf("%d\n", tot); 14 return 0; 15 }
B - Complete the Word
题意:给你一个字符串,然后问你是否存在一个长度为26连续子序列,它包含所有的26个字母
思路:水。
1 #include <set> 2 #include <map> 3 #include <cmath> 4 #include <stack> 5 #include <queue> 6 #include <cstdio> 7 #include <vector> 8 #include <cstring> 9 #include <iostream> 10 #include <algorithm> 11 using namespace std; 12 typedef long long LL; 13 #define mem(x,y) memset(x, y, sizeof(x)) 14 #define lson l,m,rt << 1 15 #define rson m+1,r,rt << 1 | 1 16 int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);} 17 int lcm(int a, int b){return a / gcd(a, b) * b;} 18 int vis[30]; 19 char s[50000 + 5]; 20 int main() 21 { 22 23 scanf("%s", s); 24 int len = strlen(s); 25 int ok = 0; 26 if(len >= 26) 27 { 28 for(int i = 0; i <= len - 26; i++) 29 { 30 mem(vis, 0); 31 for(int j = 0; j < 26; j++) 32 { 33 char t = s[i + j]; 34 35 if(t != ‘?‘ && !vis[t - ‘A‘]) vis[t - ‘A‘] = 1; 36 else if(t != ‘?‘) break; 37 if(j == 25) ok = 1; 38 } 39 40 if(ok) 41 { 42 for(int j = 0; j < 26; j++) 43 { 44 if(s[i + j] == ‘?‘) 45 { 46 for(int k = 0; k < 26; k++) 47 { 48 if(!vis[k]) 49 { 50 s[i + j] = ‘A‘ + k; 51 vis[k] = 1; 52 break; 53 } 54 } 55 } 56 } 57 break; 58 } 59 } 60 } 61 if(ok) 62 { 63 for(int i = 0; i < len; i++) 64 { 65 if(s[i] == ‘?‘) s[i] = ‘A‘; 66 printf("%c", s[i]); 67 } 68 puts(""); 69 } 70 else 71 { 72 puts("-1"); 73 } 74 75 return 0; 76 }
C - Plus and Square Root
题意:
思路:
1 #include <set> 2 #include <map> 3 #include <cmath> 4 #include <stack> 5 #include <queue> 6 #include <cstdio> 7 #include <vector> 8 #include <cstring> 9 #include <iostream> 10 #include <algorithm> 11 using namespace std; 12 typedef long long LL; 13 #define mem(x,y) memset(x, y, sizeof(x)) 14 #define lson l,m,rt << 1 15 #define rson m+1,r,rt << 1 | 1 16 int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);} 17 int lcm(int a, int b){return a / gcd(a, b) * b;} 18 19 int main() 20 { 21 int n; 22 scanf("%d", &n); 23 printf("%d\n", 2); 24 for(int i = 2; i <= n ; i++) 25 { 26 printf("%I64d\n", (LL)i * (i + 1) * (i + 1) - (i - 1)); 27 } 28 29 return 0; 30 }
Codeforces Round #372
Codeforces Round #373
Codeforces Round #374
Codeforces Round #375
Codeforces Round #376
Codeforces Round #377
Codeforces Round #378
Codeforces Round #379
Codeforces Round #370 - #379 (Div. 2)