本文共 12905 字，大约阅读时间需要 43 分钟。
好久没更博了，还是象征性地更一次。
依然延续了简要题解的风格。
题目链接
题解
A. 迫真字符串
记 \(s_i\) 表示数字 \(i\) 出现的次数，答案为 \(\min\{\lfloor\frac{s_1}{3}\rfloor, \lfloor\frac{s_4}{2}\rfloor, s_5\}\)。
#include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); string s; cin >> s; int a = 0, b = 0, c = 0, n = s.length(); for (int i = 0; i < n; ++i) { if (s[i] == '1') { ++a; } else if (s[i] == '4') { ++b; } else if (s[i] == '5') { ++c; } } cout << min(min(a / 3, b / 2), c) << '\n'; return 0;}
B. 迫真数论
暴力。
#include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tt; long long n; cin >> tt; while (tt--) { cin >> n; int answer = 0; auto f = [&] (int x) { int result = 0; while (x) { result += x % 10; x /= 10; } return result; }; for (int i = 1; i <= 200; ++i) { if (n % i == 0 && f(i) == (i >> 1)) { ++answer; } } cout << answer << '\n'; } return 0;}
C. 迫真小游戏
贪心。
#include using namespace std;const int N = 567890;int n, a[N], depth[N];vector adj[N], nodes[N];bool visit[N];void dfs(int x, int f) { nodes[depth[x] = depth[f] + 1].push_back(x); for (auto y : adj[x]) { if (y != f) { dfs(y, x); } }}int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1, x, y; i < n; ++i) { cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } dfs(1, 0); for (int i = 1; i <= n; ++i) { cin >> a[i]; } multiset s; priority_queue
, greater
> q; for (int i = 2; i <= n; ++i) { s.insert(a[i]); } cout << 1 << " \n"[n == 1]; int j = 1, tt = 1; while (tt != n) { while (s.size() && j < *s.begin()) { ++j; for (auto x : nodes[j]) { q.push(x); } } int x = q.top(); s.erase(s.find(a[x])); q.pop(); cout << x << " \n"[++tt == n]; } return 0;}
D. 迫真图论
假设 \(n, m\) 同阶。将点按度数大小是否超过 \(\sqrt n\) 分类，记为大点和小点，那么小点的度数不超过 \(\sqrt n\)，大点的总数量不超过 \(O(\sqrt n)\)，这样就可以暴力做了。对于每个大点，用一棵 trie 维护与其相邻的小点间的边的信息；对于所有小点与小点间的边、大点与大点间的边的信息，可以用一棵全局的树状数组维护。大点的权值对 trie 的影响可以用一个tag标记记录，剩下的修改与查询操作就比较显然了。
在代码实现中，点按度数大小分类的阈值可以设得比 \(\sqrt n\) 稍大一些。
#include using namespace std;const int N = 1 << 18, sq = 2000, mod = 998244353;int n, m, q, tt, degree[N], a[N], x[N], y[N], z[N], ch[N * 100][2], root[N], tag[N], now_tag;vector > adj[N], sadj[N];long long sum[N * 100];bool type[N];class bit { long long a[N]; public: bit() { memset(a, 0, sizeof a); } void add(int x, int y) { if (!x) { a[0] += y; return; } while (x < N) { a[x] += y; x += x & -x; } } long long sum(int x) { long long result = a[0]; while (x) { result += a[x]; x -= x & -x; } return result; }} tree;void insert(int& x, int d, int y, int z, int now_tag) { if (!x) { x = ++tt; } sum[x] += z; if (!~d) { return; } insert(ch[x][(y >> d & 1) ^ (now_tag >> d & 1)], d - 1, y, z, now_tag);}long long query(int x, int d, int y, int now_tag) { if (!x) { return 0; } if (!~d) { return sum[x]; } if (y >> d & 1) { if (now_tag >> d & 1) { return sum[ch[x][1]] + query(ch[x][0], d - 1, y, now_tag); } else { return sum[ch[x][0]] + query(ch[x][1], d - 1, y, now_tag); } } else { if (now_tag >> d & 1) { return query(ch[x][1], d - 1, y, now_tag); } else { return query(ch[x][0], d - 1, y, now_tag); } }}int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m >> q; for (int i = 1; i <= n; ++i) { cin >> a[i]; } for (int i = 1; i <= m; ++i) { cin >> x[i] >> y[i] >> z[i]; adj[x[i]].emplace_back(y[i], i); adj[y[i]].emplace_back(x[i], i); ++degree[x[i]]; ++degree[y[i]]; } for (int i = 1; i <= n; ++i) { if (degree[i] <= sq) { type[i] = false; } else { type[i] = true; } } vector snodes; for (int i = 1; i <= n; ++i) { if (type[i]) { tag[i] = a[i]; snodes.push_back(i); for (auto p : adj[i]) { if (type[p.first]) { sadj[i].push_back(p); } } } } for (int i = 1; i <= n; ++i) { for (auto p : adj[i]) { int j = p.first; if (type[i] == type[j] && i < j) { tree.add(a[i] ^ a[j], z[p.second]); } else if (type[i] && !type[j]) { insert(root[i], 16, a[i] ^ a[j], z[p.second], tag[i]); } } } for (int i = 1, op, u, v; i <= q; ++i) { cin >> op >> u >> v; if (op == 1) { if (!type[u]) { for (auto p : adj[u]) { if (!type[p.first]) { tree.add(a[u] ^ a[p.first], -z[p.second]); tree.add(v ^ a[p.first], z[p.second]); } else { insert(root[p.first], 16, a[u] ^ a[p.first], -z[p.second], tag[p.first]); insert(root[p.first], 16, v ^ a[p.first], z[p.second], tag[p.first]); } } } else { tag[u] ^= a[u] ^ v; for (auto p : sadj[u]) { tree.add(a[u] ^ a[p.first], -z[p.second]); tree.add(v ^ a[p.first], z[p.second]); } } a[u] = v; } else if (op == 2) { int s = x[u], t = y[u]; if (type[s] == type[t]) { tree.add(a[s] ^ a[t], -z[u]); tree.add(a[s] ^ a[t], v); } else { if (type[t]) { swap(s, t); } insert(root[s], 16, a[s] ^ a[t], -z[u], tag[s]); insert(root[s], 16, a[s] ^ a[t], v, tag[s]); } z[u] = v; } else { --u; long long answer = tree.sum(v) - (~u ? tree.sum(u) : 0); for (auto x : snodes) { answer += query(root[x], 16, v, tag[x]) - (~u ? query(root[x], 16, u, tag[x]) : 0); } cout << (answer % mod) << '\n'; } } return 0;}
E. 迫真大游戏
先只考虑 \(1\) 号分身。定义 \(f_i\) 表示当前还剩 \(i\) 个分身（必然包含 \(1\) 号分身），\(1\) 号分身最后消失的概率。那么有 \(f_i = \sum_\limits{j = 1}^i \binom{i - 1}{j - 1} (1 - p)^{j}p^{i- j}f_j\)，\(f_1 = 1\)，可以用分治 NTT 在 \(O(n \log^2 n)\) 的时间内求出所有 \(f_i\)，那么 \(1\) 号分身的答案即为 \(f_n\)。
现在考虑求其他分身的答案。为了让 \(x\) 号分身的答案也能用 \(f_i\) 求出，我们可以直接枚举前 \(x - 1\) 个人的消失情况，然后乘以对应的方案数和概率，发现又是一个卷积的形式，于是再做一次 NTT 即可。
#include using namespace std;const int N = 567890, mod = 998244353, root = 3;void add(int& x, int y) { x += y; if (x >= mod) { x -= mod; }}int mul(int x, int y) { return (long long) x * y % mod;}int qpow(int x, int y) { int result = 1; for (; y; y >>= 1, x = mul(x, x)) { if (y & 1) { result = mul(result, x); } } return result;}int n, a, b, p, rev[N], f[N], fac[N], ifac[N], inv[N];void dft(vector & buffer, bool inv = false) { int n = buffer.size(); for (int i = 0; i < n; ++i) { if (i < rev[i]) { swap(buffer[i], buffer[rev[i]]); } } for (int i = 1; i < n; i <<= 1) { int x = qpow(root, inv ? mod - 1 - (mod - 1) / (i << 1) : (mod - 1) / (i << 1)); for (int j = 0; j < n; j += i << 1) { int y = 1; for (int k = 0; k < i; ++k, y = mul(y, x)) { int p = buffer[j + k], q = mul(y, buffer[i + j + k]); buffer[j + k] = (p + q) % mod; buffer[i + j + k] = (p - q + mod) % mod; } } } if (inv) { int x = qpow(n, mod - 2); for (int i = 0; i < n; ++i) { buffer[i] = mul(buffer[i], x); } }}vector pmul(vector x, vector y) { int n = x.size() + y.size() - 1, len = 0; for (; (1 << len) < n; ++len); for (int i = 0; i < (1 << len); ++i) { rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << len - 1); } x.resize(1 << len); y.resize(1 << len); dft(x); dft(y); for (int i = 0; i < (1 << len); ++i) { x[i] = mul(x[i], y[i]); } dft(x, true); x.resize(n); return x;}void solve(int l, int r) { if (l == r) { if (l == 1) { f[1] = 1; } else { f[l] = mul(f[l], fac[l - 1]); f[l] = mul(f[l], qpow(1 - qpow(1 - p + mod, l) + mod, mod - 2)); } } else { int mid = l + r >> 1; solve(l, mid); vector foo(mid - l + 1), bar(r - l); for (int i = l; i <= mid; ++i) { foo[i - l] = mul(f[i], mul(qpow(1 - p + mod, i), ifac[i - 1])); } for (int i = 1; i <= r - l; ++i) { bar[i - 1] = mul(qpow(p, i), ifac[i]); } foo = pmul(foo, bar); for (int i = mid + 1; i <= r; ++i) { add(f[i], foo[i - l - 1]); } solve(mid + 1, r); }}int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> a >> b; p = mul(a, qpow(b, mod - 2)); fac[0] = ifac[0] = inv[1] = fac[1] = ifac[1] = 1; for (int i = 2; i <= n; ++i) { inv[i] = mul(mod - mod / i, inv[mod % i]); fac[i] = mul(fac[i - 1], i); ifac[i] = mul(ifac[i - 1], inv[i]); } solve(1, n); vector foo(n), bar(n); for (int i = 0; i < n; ++i) { foo[i] = mul(f[n - i], mul(qpow(p, i), ifac[i])); bar[i] = mul(qpow(1 - p + mod, i), ifac[i]); } foo = pmul(foo, bar); for (int i = 0; i < n; ++i) { cout << mul(foo[i], fac[i]) << '\n'; } return 0;}
F. 迫真树
二分答案 \(k\) 后通过做 dp 来判断是否存在合法方案。假设整棵树以 \(1\) 为根，设 \(f_{i, j}\) 表示 \(i\) 号点往子树内延伸的最长链长度为 \(j\)，且子树合法（即子树内最长链不超过 \(k\)）的最小代价（\(f_{i, 0}\) 则表示不选 \(i\) 点的最小代价），那么转移比较显然。注意到 dp 状态的第二维与点往下延伸的最长链长度有关，那么考虑用长链剖分，对 dp 转移分情况讨论后发现需要用到一段区间内的最优 dp 值，用线段树维护即可。
#include using namespace std;const int N = 123456;const long long llinf = 1e18;int n, m, tt, a[N], heavy[N], dfn[N], maxd[N];vector adj[N];long long dp0[N];class segment_t { long long a[N << 2], tag[N << 2]; public: segment_t() { fill(a, a + (N << 2), llinf); memset(tag, 0, sizeof tag); } void mark(int x, long long y) { tag[x] += y; a[x] += y; } void push(int x) { if (tag[x]) { mark(x << 1, tag[x]); mark(x << 1 | 1, tag[x]); tag[x] = 0; } } void modify(int l, int r, int x, int ql, int qr, long long y) { if (ql <= l && r <= qr) { mark(x, y); } else { int mid = l + r >> 1; push(x); if (ql <= mid) { modify(l, mid, x << 1, ql, qr, y); } if (qr > mid) { modify(mid + 1, r, x << 1 | 1, ql, qr, y); } a[x] = min(a[x << 1], a[x << 1 | 1]); } } void modify(int l, int r, int x, int p, long long y) { if (l == r) { a[x] = min(a[x], y); } else { int mid = l + r >> 1; push(x); if (p <= mid) { modify(l, mid, x << 1, p, y); } else { modify(mid + 1, r, x << 1 | 1, p, y); } a[x] = min(a[x << 1], a[x << 1 | 1]); } } long long query(int l, int r, int x, int ql, int qr) { if (ql <= l && r <= qr) { return a[x]; } else { int mid = l + r >> 1; long long result = llinf; push(x); if (ql <= mid) { result = min(result, query(l, mid, x << 1, ql, qr)); } if (qr > mid) { result = min(result, query(mid + 1, r, x << 1 | 1, ql, qr)); } return result; } }};void dfs(int x, int f) { maxd[x] = -1; for (auto y : adj[x]) { if (y != f) { dfs(y, x); if (maxd[y] > maxd[x]) { heavy[x] = y; maxd[x] = maxd[y]; } } } ++maxd[x];}bool check(int k) { segment_t tree; auto dp = [&] (int x, int y) { return !y ? dp0[x] : tree.query(1, n, 1, dfn[x] + y - 1, dfn[x] + y - 1); }; function dfs = [&] (int x, int f) { dp0[x] = a[x]; dfn[x] = ++tt; if (maxd[x]) { dfs(heavy[x], x); dp0[x] += min(dp(heavy[x], 0), tree.query(1, n, 1, dfn[heavy[x]], dfn[heavy[x]] + min(maxd[heavy[x]], k - 1))); tree.modify(1, n, 1, dfn[x], dp(heavy[x], 0)); } else { tree.modify(1, n, 1, dfn[x], 0); } for (auto y : adj[x]) { if (y != f && y != heavy[x]) { dfs(y, x); dp0[x] += min(dp(y, 0), tree.query(1, n, 1, dfn[y], dfn[y] + min(maxd[y], k - 1))); vector foo; vector > bar; for (int j = 1; j <= min(maxd[y] + 2, k); ++j) { int l = 1, r = min(j, k - j + 1); if (l > r) { break; } long long t = dp(y, j - 1); foo.push_back(t + tree.query(1, n, 1, dfn[x] + l - 1, dfn[x] + r - 1)); if (!bar.size() || (bar.size() && t < bar.back().second)) { bar.emplace_back(j - 1, t); } } long long last = 0; for (auto p : bar) { int l = p.first + 1, r = min(maxd[x] + 1, k - p.first); if (l <= r) { tree.modify(1, n, 1, dfn[x] + l - 1, dfn[x] + r - 1, p.second - last); last = p.second; } } for (int i = 0; i < foo.size(); ++i) { tree.modify(1, n, 1, dfn[x] + i, foo[i]); } } } }; tt = 0; dfs(1, 0); return min(dp(1, 0), tree.query(1, n, 1, dfn[1], dfn[1] + min(maxd[1], k - 1))) <= m;}int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; long long all = 0; for (int i = 1; i <= n; ++i) { cin >> a[i]; all += a[i]; } if (all <= m) { cout << 0 << '\n'; exit(0); } for (int i = 1, x, y; i < n; ++i) { cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } dfs(1, 0); int l = 1, r = n; while (l != r) { int mid = l + r >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } cout << l << '\n'; return 0;}