Educational Codeforces Round 25
这一场是暑期的第一场，做了4个题，被HACK两个，都是很粗心的错误，手生的问题。
【A】Binary Protocol
题意：给你一串字符串，只有0和1。用m个0将字符串分为m+1段，每段字符串中‘1’的个数代表一个数。
做法：在末尾补0.然后扫一遍。遇到1累加，遇到0输出累加值。
注意:
1001有两个连续的0，两个0之间有0个1，所以输出0，结果101.
1110末尾为0，0的后面有0个1，所以也要输出0，结果30.
代码:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #include <bits/stdc++.h> using namespace std; int main() { string s; int len; while(cin >> len >> s) { s = s + '0'; int tp = 0; for(int i = 0; i < len+1; i++) { if(s[i] == '1') tp++; else { cout << tp; tp = 0; } } cout << endl; } } |
【B】Five-In-a-Row
题意: 五子棋，下一步是X，问能否胜利。
做法：完全暴力，枚举X的位置，然后check一下能否构成5个子。
PS：傻逼的忘了判断正斜线，被HACK了，五子棋白下了。
| 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 | #include <bits/stdc++.h> using namespace std; char mp[20][20]; bool check(int x, int y){ //列 int tp = 1; for(int i = x + 1; i < 10; i++) { if(mp[i][y] == 'X') tp++; else break; } for(int i = x - 1; i >= 0; i--) { if(mp[i][y] == 'X') tp++; else break; } if(tp >= 5) return true; //行 tp = 1; for(int j = y + 1; j < 10; j++) { if(mp[x][j] == 'X') tp++; else break; } for(int j = y - 1; j >= 0; j--) { if(mp[x][j] == 'X') tp++; else break; } if(tp >= 5) return true; //负斜线 int a = x, b = y; tp = 1; while(x >=0 && y >= 0) { x--; y--; if(x >=0 && y >= 0 && mp[x][y] == 'X') tp++; else break; } x = a, y = b; while(x < 10 && y < 10) { x++; y++; if(x < 10 && y < 10 && mp[x][y] == 'X') tp++; else break; } if(tp >= 5) return true; //正斜线 x = a, y = b; tp = 1; while(x >= 0 && y >= 0 && x < 10 && y < 10) { x--; y++; if(x >= 0 && y >= 0 && x < 10 && y < 10 && mp[x][y] == 'X') tp++; else break; } x = a, y = b; while(x >= 0 && y >= 0 && x < 10 && y < 10) { x++; y--; if(x >= 0 && y >= 0 && x < 10 && y < 10 && mp[x][y] == 'X') tp++; else break; } if(tp >= 5) return true; return false; } int main() { for(int i = 0; i < 10; i++) { scanf("%s", &mp[i]); } // 枚举X的位置 for(int i = 0; i < 10; i++) { for(int j = 0; j < 10; j++) { if(mp[i][j] == '.') { mp[i][j] = 'X'; if( check(i, j) ) { puts("YES"); return 0; } mp[i][j] = '.'; } } } puts("NO"); } |
【C】Multi-judge Solving
题意：做题。每个题有难度等级。给定Makes目前做过最难题的等级D，只要题的难度A <= 2D，那么Makes就可以做。不然Makes就要从别的OJ做任意可做难度的题。问至少需要在别的OJ做多少题。
做法：贪心。按题目难度从小到大排序。如果当前题可以做，那么就更新D；不能做就去别的OJ做一道能做的最难的题，也就是2D的难度，更新D = 2D。
代码：
| 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 | #include <bits/stdc++.h> #define LL long long using namespace std; int main() { int n; LL k; LL a[1010]; scanf("%d%I64d", &n, &k); for(int i = 0; i < n; i++) scanf("%I64d", &a[i]); sort(a, a + n); LL ans = 0; for(int i = 0; i < n; i++) { LL tp = a[i] + 1 >> 1; if(k >= tp) { k = max(k, a[i]); } else { while(k < tp) { k = 2 * k; ans ++; } k = max(k, a[i]); } } cout << ans << endl; } |
【D】 Suitable Replacement
题意：给定2个字符串。A字符串的?可以是任意小写字母。让你补齐?，任意调整顺序，使得A字符串包含最多个B字符串 。
做法：模拟构造。先计算第B字符串对每个字母的消耗量，例如aabbc，则consum['a'] = 2, consum['b'] = 2, consum['c'] = 1。
累计A字符串各个字符的个数。计算A字符串可以减去多少 “波“B字符串 ，不够用‘？‘来代替，直至’？‘不够用。输出构造结果，剩余的’？‘随便用一个字母补齐。
代码:
| 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 | #include <bits/stdc++.h> using namespace std; int node[200]; //A字符串中各个字符的个数 int main() { string s, t; memset(node, 0, sizeof(node)); cin >> s >> t; //判断是否存在? bool f = true; for(int i = 0; i < s.size(); i++) { if(s[i] == '?') f = false; } if(f) { cout << s << endl; return 0; } map<char, int>mp; //B字符串各个字符的个数 vector<char>vec; //存B字符串的N个字符 for(int i = 0; i < t.size(); i++) { mp[t[i]]++; if(mp[t[i]] == 1) vec.push_back(t[i]); } int len = 0; //问号个数 for(int i = 0; i < s.size(); i++) { if(s[i] == '?') len++; else if(mp[s[i]]) { node[s[i]]++; } } vector<char>ans; while(len > 0) { for(int i = 0; i < vec.size(); i++) { node[vec[i]] -= mp[vec[i]]; if(node[vec[i]] < 0) { len += node[vec[i]]; if(len < 0) break; int n = -node[vec[i]]; while(n--) ans.push_back(vec[i]); node[vec[i]] = 0; } } } int idx = 0; for(int i = 0; i < s.size(); i++) { if(s[i] == '?') { if(idx < ans.size()) { s[i] = ans[idx]; idx++; } else { s[i] = 'a'; } } } cout << s << endl; } |
【E】Minimal Labels
题意：给定你一个不一定联通的无环有向图，让你构造一个序列ans[]。定义：u -> v， 那么 ans[u] < ans[v]。并且要求构造出来的序列的字典序最小。
做法：因为无环，所以一定存在出度为0的点，且出度为0的点构造的值一定是最大的，不难看出，如果是连通图，那么结果是一定的。如果是非连通图，那就存在优先问题，为了让字典序最小，我们肯定是先给点小的点赋大值。
因此，用set来存出度为0的点，每次弹出一个最小的点，赋最大值，删除指向它的边，同时更新出度为0的点。
代码:
| 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 | #include <bits/stdc++.h> using namespace std; vector<int>in[100010]; vector<int>out[100010]; int main () { int n, m, v, u; scanf("%d%d", &n, &m); set<int, greater<int> >st; //从小到大弹出 for(int i = 1; i <= n; i++) st.insert(i); for(int i = 0; i < m; i++) { scanf("%d%d", &v, &u); in[u].push_back(v); out[v].push_back(u); st.erase(v); } int ans[100010]; int idx = n; while(!st.empty()) { int cur = *st.begin(); st.erase(st.begin()); ans[cur] = idx--; //赋最大值 //删除指向它的边，同时更新出度为0的点 for(int i = 0; i < in[cur].size(); i++) { int x = in[cur][i]; out[x].erase(find(out[x].begin(), out[x].end(), cur)); if(out[x].empty()) st.insert(x); } } bool f = false; for(int i = 1; i <= n; i++) { if(f) putchar(' '); f = true; printf("%d", ans[i]); } puts(""); } |
转载于:https://www.cnblogs.com/bestwzh/p/7223843.html
《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读总结
以上是生活随笔为你收集整理的Educational Codeforces Round 25的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： [LeetCode] Longest S
- 下一篇： 过滤器解决Struts2重定向漏洞