首页 > 代码库 > Codeforces Round #407 (Div. 2)（争取明天24点前补掉）
Codeforces Round #407 (Div. 2)（争取明天24点前补掉）
A - Anastasia and pebbles（水题）
题意：
一个人有俩口袋，每个口袋最多装k个，然后每天每个口袋里的石头颜色必须都相同，问你最少用几天能装完。
思路：
水题。。一不小心写瓷了，以为A题大水题，瞎写也不会T，没仔细想。。写了一个T的代码。
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int n, k; 6 cin >> n >> k; 7 vector<int>vec; 8 for(int i = 1; i <= n; i++) 9 { 10 int x; 11 scanf("%d", &x); 12 vec.push_back(x); 13 } 14 int ans = 0; 15 for(auto o : vec) 16 { 17 ans += (o + k - 1) / k; 18 } 19 cout << (ans + 1) / 2 <<endl; 20 return 0; 21 }
B - Masha and geometric depression（模拟）
题意：
给你一个等差数列的首项b1和公比q，还有一个上界l，但是b1和q都可以为0。又给出一个序列a，然后挨个计算出这个等差数列bi，如果bi出现在序列a中，那么就不写出来，最后问你写出来的数有几个。前提是所有的bi的绝对值都必须不超过上界l。
思路：
一开始写了一个分类讨论的，比较麻烦。。容易写wa。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 int main() 5 { 6 int b1, q, l, m; 7 cin >> b1 >>q >> l >> m; 8 9 set<LL>s; 10 for(int i = 0; i < m; i++) 11 { 12 LL x; 13 cin >> x; 14 s.insert(x); 15 } 16 17 if(abs(b1) > l) 18 { 19 puts("0"); 20 return 0; 21 } 22 23 if(b1 == 0) 24 { 25 int haveb1 = (s.find(b1) == s.end()); 26 if(haveb1) puts("inf"); 27 else puts("0"); 28 } 29 else if(q == 0) 30 { 31 LL haveb1 = (s.find(b1) == s.end()); 32 LL have0 = (s.find(0) == s.end()); 33 if(have0) puts("inf"); 34 else if(haveb1) puts("1"); 35 else puts("0"); 36 37 } 38 else if(q == 1) 39 { 40 int haveb1 = (s.find(b1) == s.end()); 41 42 if(haveb1)puts("inf"); 43 else printf("0\n"); 44 } 45 else if(q == -1) 46 { 47 int haveb1 = (s.find(b1) == s.end()); 48 int havefub1 = (s.find(-b1) == s.end()); 49 if(haveb1 || havefub1) puts("inf"); 50 else printf("0\n"); 51 52 } 53 else 54 { 55 LL ans = 0; 56 for(LL i = b1; abs(i) <= l; i *= q) 57 { 58 if(s.find(i) == s.end()) ans++; 59 } 60 cout << ans << endl; 61 } 62 return 0; 63 }
C - Functions again（最大字段和）
题意：
给你这么一个公式， 
，输出f的最大值。
数据：
(2?≤?n?≤?105)(-109?≤?ai?≤?109)
思路：
拿一两个样例比划一下，就能明白，其实就是最大字段和，扫两边，翻转一下正负号就好了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 5 LL a[100000 + 5]; 6 LL d[100000 + 5]; 7 int n; 8 LL solve() 9 { 10 LL maxx = -(1LL << 60); 11 LL temp = 0; 12 for(int i =0; i < n - 1; i++) 13 { 14 if(temp < 0) temp = d[i]; 15 else temp += d[i]; 16 maxx = max(maxx, temp); 17 } 18 return maxx ; 19 } 20 int main() 21 { 22 cin >> n; 23 for(int i = 0; i < n; i++) 24 { 25 cin >> a[i]; 26 } 27 for(int i = 0; i < n; i++) 28 { 29 d[i] = abs(a[i + 1] - a[i]); 30 if(i % 2 == 0) d[i] *= -1; 31 } 32 33 LL maxx1 = solve(); 34 35 for(int i = 0; i < n; i++) 36 { 37 d[i] *= -1; 38 } 39 40 LL maxx2 = solve(); 41 42 43 cout << max(maxx1, maxx2) << endl; 44 return 0; 45 }
D - Weird journey
E - The Great Mixing
题意：
给你一个数n，一个数k，再给k个数字，每个数字可以选择任意个数，最后问你最少使用“几个次”数字使得平均数为n。
数据：
(0?≤?n?≤?1000, 1?≤?k?≤?106) ，(0?≤?ai?≤?1000)
思路：
先统一一下度量，这k个数字ai，对最后结果的贡献应该是ai-n吧，所以先这么处理一下。然后bfs就行了。因为最多只有-1000到1000的范围，而k个数字实际上，只有最多有1000种。所以大概是1k*2k的样子。所以bfs没啥问题。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef pair<int, int>pii; 4 5 int n, k; 6 int step[2005]; 7 queue<int>que; 8 set<int>vec; 9 10 int solve() 11 { 12 while(que.size()) 13 { 14 int val = que.front();que.pop(); 15 if(val == 0) return step[val + 1000]; 16 for(auto o : vec) 17 { 18 int fval = val + o; 19 if(fval >= -1000 && fval <= 1000 && step[fval + 1000] == 0) 20 { 21 que.push(fval); 22 step[fval + 1000] = step[val + 1000] + 1; 23 } 24 } 25 } 26 return -1; 27 } 28 29 int main() 30 { 31 32 scanf("%d%d", &n, &k); 33 for(int i = 0; i < k; i ++) 34 { 35 int x; 36 scanf("%d", &x); 37 x -= n; 38 vec.insert(x); 39 que.push(x); 40 step[x + 1000] = 1; 41 } 42 printf("%d\n", solve()); 43 44 return 0; 45 }
Codeforces Round #407 (Div. 2)（争取明天24点前补掉）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。