运动会期间没啥事，来 VP 吧。5-8 晚上打的，vp 时过了 4 题，堪堪铜尾，但是实际上最后两小时的开题根本就调不出来（不知道是做法假了还是细节没考虑到）。还得多训点银牌题和铜牌思维题。
主要问题是罚时太多了，手速不够快，这在赛场上肯定被队友喷死了，晚上还窜了，真无语。。。
不过才发现罚时的重要性，其实罚时少的话那场比赛是可以 Ag 的。看了一眼榜，罚时少一点大概 rank 30 左右，罚时多的话就 rank 60 了。
补题进度：I 题、J 题、C 题
（第一次知道陕西的英文是 shaanxi 不是 shanxi）
L
考虑到数位积在 10 的倍数是一定为 0。所以暴力做，答案为 0 直接退出，最多做 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 |
#include <bits/stdc++.h> using LL = long long; constexpr int mod = 1e9 + 7; LL calc_f(int x) { LL res = 1; while (x) { res *= x % 10; res %= mod; if (not res) return 0; x /= 10; } return res % mod; } void solve() { int l, r; std::cin >> l >> r; LL res = 1; for (int i = l; i <= r and res; ++ i) { res *= calc_f(i); res %= mod; } std::cout << res << '\n'; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { solve(); } } |
E
二分答案+贪心，稍微有点小细节。
|
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 |
#include <bits/stdc++.h> using PII = std::pair<int, int>; void solve() { int n, k; std::cin >> n >> k; std::string s; std::cin >> s; s = " " + s; auto check = [&](int x) -> bool { int p = 0; for (int i = 1; i <= k; ++ i) { do p ++; while (p <= n and s[p] == '0'); p += x - 1; } if (p <= n) ++ p; for (; p <= n; ++ p) { if (s[p] == '1') return false; } return true; }; int l = 1, r = n; while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } std::cout << l << '\n'; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { solve(); } } |
K
签到，但是我 wa 了 5 发还是 6 发。不是这里没有考虑到就是哪里没考虑到，其实这些简单题做得快，可以为自己争取到非常多的优势的，但是很显然这次我没有。
|
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 |
#include <bits/stdc++.h> using LL = long long; LL solve() { LL x, y, z; std::cin >> x >> y >> z; if (x + y == z) { return z + 1; } if (x + y < z) { return -1; } LL k = x + y - z; if (x < k - 1 and z < k - 1) { return k; } return -1; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { std::cout << solve() << '\n'; } } |
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 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 86 87 |
#include <bits/stdc++.h> bool solve() { int n, m; std::cin >> n >> m; std::vector<std::string> grid(n + 1); std::vector<std::vector<int>> a(n + 1, std::vector<int>(m + 1)); for (int i = 1; i <= n; ++ i) { std::cin >> grid[i]; grid[i] = " " + grid[i]; } for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= m; ++ j) { std::cin >> a[i][j]; } } auto calc_pos = [&](int x, int y) -> int { x --, y --; return x * m + y + 1; }; std::vector<int> G(n * m + 1, -1), d(n * m + 1, 0), invG(n * m + 1, -1); for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= m; ++ j) { int tx = i, ty = j; int val = a[i][j]; char c = grid[i][j]; if (c == 'u') tx -= val; else if (c == 'd') tx += val; else if (c == 'l') ty -= val; else ty += val; if (tx < 1 or tx > n or ty < 1 or ty > m) continue; int pos1 = calc_pos(i, j), pos2 = calc_pos(tx, ty); G[pos1] = pos2; invG[pos2] = pos1; d[pos2] ++; } } auto in_point = [&]() -> int { for (int i = 1; i <= n * m; ++ i) { if (d[i] == 0) return i; } return -1; }; int in = in_point(); if (in == -1) { // 如果有环 int cur = G[1]; int cnt = 1; while (cur != 1) { cnt ++; cur = G[cur]; } return cnt == n * m; } // 如果没有环 std::vector<bool> vis(n * m + 1, false); int cur = in; int cnt = 0; while (cur != -1 and not vis[cur]) { vis[cur] = true; cnt ++; cur = G[cur]; } return cnt == n * m; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { if (solve()) std::cout << "Yes\n"; else std::cout << "No\n"; } } |
I
给出一棵树和边权，判断那些点可以成为 trie 树的根。一开始我的想法是做两次 dfs，第一次预处理出 root=1 的情况，vaild[i] 表示子树 i 是否合法，然后在 dfs 一次每一次做一次转移，也就是根据父节点的情况递推出子节点作为 root 时的 vaild 数组，当然需要修改的只有 vaild[u] 和 vaild[v]，然后对于每一个父节点只有当子树全合法，出边无相同时才合法，但是不知为啥 Wa 了，可能细节出问题了。
std 是去做一个标记，对与非法位置讨论合法根节点可能的位置。也就是使用差分数组+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 <bits/stdc++.h> int solve() { int n; std::cin >> n; std::vector<std::vector<std::pair<int, char>>> G(n + 1); for (int i = 1; i < n; ++ i) { int u, v; std::string s; std::cin >> u >> v >> s; G[u].emplace_back(v, s[0]); G[v].emplace_back(u, s[0]); } std::vector<int> dfn(n + 1), fin(n + 1); std::vector<int> f(n + 1, 0); auto add = [&](int l, int r, int v) -> void { f[l] += v; if (r + 1 <= n) f[r + 1] -= v; }; int timestamp = 0; auto dfs = [&](auto &&self, int u, int p) -> void { dfn[u] = ++ timestamp; for (auto [v, c] : G[u]) { if (v == p) continue; self(self, v, u); } fin[u] = timestamp; }; dfs(dfs, 1, 0); for (int u = 1; u <= n; ++ u) { std::vector<std::vector<int>> st(26); for (auto [v, c] : G[u]) { st[c - 'a'].push_back(v); } int cnt = 0; int x, y; for (auto &v : st) { if (v.size() > 2) return 0; if (v.size() == 2) { cnt ++, x = v[0], y = v[1]; } if (cnt > 1) return 0; } if (cnt == 0) continue; if (dfn[x] > dfn[y]) std::swap(x, y); if (dfn[u] < dfn[x]) { // u->x and u->y ==> u is father of x and y // 那么合法的节点只能在x或y的子树上 add(1, n, 1); add(dfn[x], fin[x], -1); add(dfn[y], fin[y], -1); } else { // x->u->y 合法的节点不能在u的非y子树上 add(dfn[u], fin[u], 1); add(dfn[y], fin[y], -1); } } int ans = 0; for (int i = 1; i <= n; ++ i) { f[i] += f[i - 1]; ans += f[i] == 0; } return ans; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { std::cout << solve() << '\n'; } } |
J
赛时的思路已经很接近正解了，可惜没有打出来。每一位分开考虑，从高到低，判断是否可以填 1。然后维护每一段区间取的数字。如果可以填 1 的话，每一段都要填 1。不可以的话，我们需要考虑让数字满足最小的要求，如果满足了就不需要操作了。
|
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 PII = std::pair<int, int>; void solve() { int n; std::cin >> n; std::vector<PII> a(n); std::vector<int> num(n, 0); // 表示第i个点中可以填的数字 for (auto &[x, y] : a) { std::cin >> x >> y; } int ans = 0; for (int bit = 29; bit >= 0; -- bit) { bool ok = true; // 表示当前位是否可以填1 for (int i = 0; i < n; ++ i) { int l = num[i] + (1 << bit); int r = num[i] + (1 << (bit + 1)) - 1; if (r < a[i].first || l > a[i].second) { // 无交集 ok = false; break; } } if (ok) { ans |= 1 << bit; for (int i = 0; i < n; ++ i) { num[i] |= 1 << bit; } } else { for (int i = 0; i < n; ++ i) { int l = num[i] + (1 << bit); int r = num[i] + (1 << (bit + 1)) - 1; if (r >= a[i].first && l <= a[i].second) { // 有交集 if (l <= a[i].first) num[i] |= 1 << bit; } } } } std::cout << ans << "\n"; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { solve(); } } |
C
考场时的思路是考虑减去所有回文，遂打了一个马拉车变体，但是发现 Wa 了。看到题解才知道需要统计的是端点不同的字符串，回文串重复考虑了很多情况。而对于翻转之后的数组，需要考虑是否有和原串相同的情况，相同则答案加一。
|
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 |
#include <bits/stdc++.h> using LL = long long; void solve() { std::string s; std::cin >> s; int n = s.size(); // 对于 [l,r] 统计满足 s[l]!=s[r] 的个数 // 考虑用总数减去满足 s[l]==s[r] 的个数 LL ans = (LL)n * (n + 1) / 2; std::vector<int> cnt(10, 0); for (auto ch : s) { int num = ch - '0'; cnt[num] ++; if (num == 0) ans -= cnt[0]; else if (num == 8) ans -= cnt[8]; else if (num == 6) ans -= cnt[9]; else ans -= cnt[6]; } bool flag = false; if (s.find('0') != std::string::npos or s.find('8') != std::string::npos or s.find("69") != std::string::npos or s.find("96") != std::string::npos) { flag = true; } std::cout << ans + flag << "\n"; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { solve(); } } |
发表回复