Codeforces Round 606 (Div. 2, based on Technocup 2020 Elimination Round 4)
oi
感觉这场 Div.2 有点水啊, 为什么我这个 AFO 的选手都能过 5 道题...
A. Happy Birthday, Polycarp!
签到题, 不多说.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 int main () { int tcnt = read (); for (int T = 1 ; T <= tcnt; T++) { int n = read (); int t = n; int dig = 0 ; while (t > 0 ) { dig++; t /= 10 ; } int ans = 9 * (dig - 1 ); int64 x = 0 ; for (int i = 1 ; i <= dig; i++) { x *= 10 ; x += 1 ; } for (int i = 1 ; i <= 9 ; i++) { if (x * i <= n) ans++; } cout << ans << endl; } }
B. Make Them Odd
每次贪心处理当前最大的偶数, 优先队列模拟即可.
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 int main () { int tcnt = read (); for (int T = 1 ; T <= tcnt; T++) { int n = read (); priority_queue<int > q; for (int i = 1 ; i <= n; i++) { int x = read (); if (!(x & 1 )) q.push (x); } int ans = 0 ; int c = 0 ; while (!q.empty ()) { int u = q.top (); q.pop (); if (u != c) { c = u; ans++; } if ((u >> 1 ) & 1 ) continue ; q.push (u >> 1 ); } write (ans); putchar ('\n' ); } }
C. As Simple as One and Two
不难发现, 对于 one
, 删掉 n
总是可行的; 对于 two
, 删掉 w
总是可行的; 但是对于 twone
的情况, 最优解是删掉 o
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 int main () { int tcnt = read (); for (int T = 1 ; T <= tcnt; T++) { scanf ("%s" , s + 1 ); int n = strlen (s + 1 ); for (int i = 1 ; i <= n; i++) { vis[i] = false ; } int ans = 0 ; for (int i = 1 ; i <= n; i++) { if (vis[i]) continue ; if (s[i] == 't' && s[i + 1 ] == 'w' && s[i + 2 ] == 'o' && s[i + 3 ] == 'n' && s[i + 4 ] == 'e' ) { vis[i + 2 ] = true ; ans++; } else if (s[i] == 't' && s[i + 1 ] == 'w' && s[i + 2 ] == 'o' ) { vis[i + 1 ] = true ; ans++; } else if (s[i] == 'o' && s[i + 1 ] == 'n' && s[i + 2 ] == 'e' ) { vis[i + 1 ] = true ; ans++; } } write (ans); putchar ('\n' ); for (int i = 1 ; i <= n; i++) { if (vis[i]) { write (i); putchar (' ' ); } } putchar ('\n' ); } }
D. Let's Play the Words?
00
和 11
的不用反转, 只用反转 01
或 10
使得两者数量只差 1 个就总是可行的; 对于能不能翻转直接用 unordered_set
维护. 注意同时包含 00
和 11
并且没有 01
或 10
是无解的, 特判输出(在这里挂了一次).
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 int main () { int tcnt = read (); for (int T = 1 ; T <= tcnt; T++) { vector<pair<int , string>> s01, s10; int c00 = 0 , c11 = 0 ; int n = read (); for (int i = 1 ; i <= n; i++) { string s; cin >> s; if (s.front () == '0' ) { if (s.back () == '0' ) c00++; else s01.push_back (make_pair (i, s)); } else { if (s.back () == '0' ) s10.push_back (make_pair (i, s)); else c11++; } } if (c00 > 0 && c11 > 0 && s01.size () + s10.size () == 0 ) { puts ("-1" ); continue ; } int d = abs ((int )s01.size () - (int )s10.size ()) / 2 ; if (s01.size () > s10.size ()) swap (s01, s10); unordered_set<string> s; vector<int > ans; for (auto i : s01) { s.insert (i.second); } for (auto i : s10) { if (ans.size () >= d) break ; string rev (i.second.rbegin(), i.second.rend()) ; if (s.count (rev) == 0 ) { ans.push_back (i.first); s.insert (rev); } } if (ans.size () < d) { puts ("-1" ); } else { write (ans.size ()); putchar ('\n' ); for (auto i : ans) { write (i); putchar (' ' ); } putchar ('\n' ); } } }
E. Two Fairs
从两个点分别做一次 DFS 就可以了, 满足要求的点对一定有一个只有 A 能 DFS 到, 另一个只有 B 能 DFS 到, 详情见代码.
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 #include <algorithm> #include <cstdio> #include <cstring> #include <iostream> #include <vector> using namespace std;typedef long long int64;const int MAXN = 200010 ;const int INF = 0x3f3f3f3f ;class lfs { public : lfs (int N) { n = N; head = new int [n + 2 ]; memset (head, -1 , (sizeof n) * (n + 2 )); ecnt = 0 ; } void adde (int from, int to, int w) { edge cur; cur.to = to; cur.w = w; cur.next = head[from]; head[from] = ecnt++; e.push_back (cur); } void addde (int a, int b, int w) { adde (a, b, w); adde (b, a, w); } int64 solve (int a, int b) { vis1 = new bool [n + 2 ]; memset (vis1, false , (sizeof false ) * (n + 2 )); vis2 = new bool [n + 2 ]; memset (vis2, false , (sizeof false ) * (n + 2 )); this ->a = a; this ->b = b; dfs (a, 0 , vis1); dfs (b, 0 , vis2); int64 cnt1 = 0 , cnt2 = 0 ; for (int i = 1 ; i <= n; i++) { if (vis1[i] && !vis2[i]) cnt1++; else if (!vis1[i] && vis2[i]) cnt2++; } return (cnt1 - 1 ) * (cnt2 - 1 ); } ~lfs () { delete [] head; delete [] vis1; delete [] vis2; } protected : struct edge { int to, next, w; }; vector<edge> e; int * head; int ecnt; int n; int a, b; bool * vis1; bool * vis2; void dfs (int u, int fa, bool * vis) { vis[u] = true ; for (int i = head[u]; i != -1 ; i = e[i].next) { int v = e[i].to; if (v != fa && v != a && v != b) { if (!vis[v]) dfs (v, u, vis); } } } };
可惜 15 号白天的两场 Div.2 都没时间打了, 不过下个星期六还有一次国人场.