CodeForces Gym 101754 简要题解

Letters Swap

首先考虑如何判断合法，不难发现拿个栈能消就消一定是正确的。

考虑分治，处理从 [l,mid] [ l , m i d ] 和 [mid+1,r] [ m i d + 1 , r ] 中选出数交换的合法方案数，记 A A 表示 [1,l−1][1,l−1] 消完剩下的串， B B 表示 [r 1,n][r 1,n] 消完剩下的串，枚举左边交换的字符的位置和交换后的字符，那么会带来 [l,mid] [ l , m i d ] 的前后缀不断消，消的长度可以通过二分哈希来判断，右边同理，然后要求左边消完拼起来的串要等于右边消完拼起来的串，也可以通过哈希统计。

#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } const int N = 100005; const int bas1 = 2333333; const int bas2 = 6666666; const int mod1 = 1e9 + 7; const int mod2 = 1e9 + 9; struct Info { int x, y; Info(int x = 0, int y = 0):x(x), y(y) {} Info operator + (const Info &b) const { return Info((x + b.x) % mod1, (y + b.y) % mod2); } Info operator - (const Info &b) const { return Info((x - b.x + mod1) % mod1, (y - b.y + mod2) % mod2); } Info operator * (const Info &b) const { return Info(1LL * x * b.x % mod1, 1LL * y * b.y % mod2); } Info operator + (const int &b) const { return Info((x + b) % mod1, (y + b) % mod2); } Info operator * (const int &b) const { return Info(1LL * x * b % mod1, 1LL * y * b % mod2); } bool operator < (const Info &b) const { return x < b.x || (x == b.x && y < b.y); } bool operator == (const Info &b) const { return x == b.x && y == b.y; } } pwd[N]; map <Info, int> cnt[9]; char s[N]; LL ans; int n; struct String { vector <Info> u, v; vector <char> w; int cur; String(int tmp = 0) { u.pb(Info(0, 0)), v.pb(Info(0, 0)), w.pb(0), cur = tmp; } inline int Size() { return w.size() - 1; } inline void Insert(char c) { u.pb(u.back() * pwd[1] + c), v.pb(v.back() + pwd[w.size() - 1] * (int)c), w.pb(c); } inline void Delete() { u.pop_back(), v.pop_back(), w.pop_back(); } inline void Extend(char c) { if (c == w.back()) { Delete(); } else { Insert(c); } } inline void MoveA(int x) { CheckMax(x, 0); for (; cur < x; Extend(s[++cur])); for (; cur > x; Extend(s[cur--])); } inline void MoveB(int x) { CheckMin(x, n + 1); for (; cur < x; Extend(s[cur++])); for (; cur > x; Extend(s[--cur])); } inline Info Query(int len) { return u.back() - u[u.size() - 1 - len] * pwd[len]; } } A, B; inline Info Merge(String &L, char c, String &R) { L.Extend(c); int l = 1, r = min(L.Size(), R.Size()), ret = 0; while (l <= r) { int mid = l + r >> 1; if (L.Query(mid) == R.Query(mid)) { ret = mid, l = mid + 1; } else { r = mid - 1; } } Info cur = L.u[L.Size() - ret] * pwd[R.Size() - ret] + R.v[R.Size() - ret]; L.Extend(c); return cur; } inline void Solve(int l, int r) { if (l == r) { return ; } int mid = l + r >> 1; String L(mid + 1), R(mid); A.MoveA(mid - 1), B.MoveB(mid + 2); for (int i = 0; i < 9; ++i) { cnt[i].clear(); } for (int i = mid; i >= l; --i) { for (char c = 'a'; c <= 'c'; ++c) { if (s[i] != c) { ++cnt[(s[i] - 'a') * 3 + c - 'a'][Merge(A, c, L)]; } } A.MoveA(i - 2), L.MoveB(i); } for (int i = mid + 1; i <= r; ++i) { for (char c = 'a'; c <= 'c'; ++c) { if (s[i] != c) { ans += cnt[(c - 'a') * 3 + s[i] - 'a'][Merge(B, c, R)]; } } B.MoveB(i + 2), R.MoveA(i); } Solve(l, mid), Solve(mid + 1, r); } int main() { #ifdef wxh010910 freopen("d.in", "r", stdin); #endif scanf("%s", s + 1), n = strlen(s + 1); pwd[0] = Info(1, 1), pwd[1] = Info(bas1, bas2); for (int i = 2; i <= n; ++i) { pwd[i] = pwd[i - 1] * pwd[1]; } A.cur = 0, B.cur = n + 1; Solve(1, n); printf("%lld\n", ans); #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }

Big Data

最优方案一定是：向下走到 A A 最大值第一次出现的位置，然后向右走到 BB 最大值，然后向下走到 A A 最大值最后出现的位置，然后向右走到底，然后向下走到底。

#include <bits/stdc .h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } const int N = 100005; int n, m, p, q, max_a, max_b, sum_a, sum_b, a[N], b[N]; int main() { #ifdef wxh010910 freopen("d.in", "r", stdin); #endif Read(n), Read(m), max_a = max_b = -1; for (int i = 1; i <= n; i) { Read(a[i]), sum_a = a[i]; if (CheckMax(max_a, a[i])) { p = i; } if (max_a == a[i]) { q = i; } } for (int i = 1; i <= m; i) { Read(b[i]), sum_b = b[i]; CheckMax(max_b, b[i]); } sum_a = max_a * (m - 1), sum_b = b[1] * (p - 1) b[m] * (n - q) max_b * (q - p); printf("%lld\n", 1000000000LL * sum_a sum_b); #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }

World of Darkraft 3

枚举用几次群体伤害然后贪心。

#include <bits/stdc .h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } const int N = 105; int n, m, a, b, c, d, ans, e[N]; int main() { #ifdef wxh010910 freopen("d.in", "r", stdin); #endif Read(n), Read(m), Read(a), Read(b), Read(c), Read(d); for (int i = 1; i <= n; i) { Read(e[i]); } sort(e 1, e n 1); for (int i = 0; i <= m / d; i) { int cur = (m - i * d) / b, dam = i * c, ret = 0; for (int j = 1; j <= n; j) { if (e[j] <= dam) { ret; } else { int tmp = (e[j] - dam a - 1) / a; if (cur < tmp) { break; } else { cur -= tmp, ret; } } } CheckMax(ans, ret); } printf("%d\n", ans); #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }

Sports Analytics

考虑容斥，将 aiai 严格小于 ai+1 a i + 1 的缩成一段，那么如果知道了一段的所有的值，那么它们对应的值也是确定的。

假设最后每段长度为 ai a i ，分配的方案数为 n!∏ai! n ! ∏ a i ! ，可以通过暴力DP计算答案。

#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } const int N = 1005; const int mod = 998244353; int n, m, f[N], inv[N]; inline int Qow(int x, int y) { int r = 1; for (; y; y >>= 1, x = 1LL * x * x % mod) { if (y & 1) { r = 1LL * r * x % mod; } } return r; } int main() { #ifdef wxh010910 freopen("d.in", "r", stdin); #endif Read(n), Read(m), inv[0] = inv[1] = f[0] = 1; for (int i = 2; i <= n; ++i) { inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod; } for (int i = 2; i <= n; ++i) { inv[i] = 1LL * inv[i - 1] * inv[i] % mod; } for (int i = 1; i <= n; ++i) { inv[i] = Qow(inv[i], m); } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= i; ++j) { if (j & 1) { f[i] = (1LL * f[i - j] * inv[j] + f[i]) % mod; } else { f[i] = (f[i] - 1LL * f[i - j] * inv[j] % mod + mod) % mod; } } } for (int i = 1; i <= n; ++i) { f[n] = 1LL * f[n] * i % mod; } printf("%d\n", f[n]); #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }

Bonsai

不难发现两棵树相等等价于它们的DFS序的节点深度相等。

注意到两个操作实际都是从深度序列删除一个元素，而反过来，从深度唯一不能表示的就是一个节点只有一个儿子的情况，但注意到在最优解中要么他和他儿子都被删除要么都保留，然后就变成了求最长公共子序列。

#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } const int N = 5005; int n, m, top, a[N], b[N], dep[N], f[N][N]; vector <int> adj[N], adv[N]; inline void DFS(int x, int *a, vector <int> *adj) { a[++top] = dep[x]; for (auto y : adj[x]) { DFS(y, a, adj); } } int main() { #ifdef wxh010910 freopen("d.in", "r", stdin); #endif Read(n), top = 0; for (int i = 2, x; i <= n; ++i) { Read(x), dep[i] = dep[x] + 1, adj[x].pb(i); } DFS(1, a, adj); Read(m), top = 0; for (int i = 2, x; i <= m; ++i) { Read(x), dep[i] = dep[x] + 1, adv[x].pb(i); } DFS(1, b, adv); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (a[i] == b[j]) { f[i][j] = f[i - 1][j - 1] + 1; } else { f[i][j] = max(f[i - 1][j], f[i][j - 1]); } } } printf("%d\n", n + m - (f[n][m] << 1)); #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }

Alfred and Georg

考虑差分，转化成每次选择 a1,a2,⋯,an a 1 , a 2 , ⋯ , a n 并将 (i,ai) ( i , a i ) 取反，要求 ai a i 单调不降。

从右往左用两个set维护路径的轮廓线即可。

#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } const int N = 1000005; const int inf = 0x3f3f3f3f; int n, m, k, ans, sum[N]; vector <int> seq, all[N]; set <int> s, t; pii a[N]; int main() { #ifdef wxh010910 freopen("d.in", "r", stdin); #endif Read(m), Read(n), Read(k); for (int i = 1; i <= k; ++i) { Read(a[i].Y), Read(a[i].X); ++a[i].X, ++a[i].Y; } sort(a + 1, a + k + 1); for (int i = 1, j = 1; i <= k; i = j) { int lst = -1; for (; j <= k && a[j].X == a[i].X; ++j) { if (~lst && lst + 1 < a[j].Y) { all[a[i].X].pb(lst + 1); } if (a[j].Y > lst + 1) { all[a[i].X].pb(a[j].Y); } lst = a[j].Y; } if (lst < m) { all[a[i].X].pb(lst + 1); } } for (int i = n; i; --i) { for (auto x : all[i]) { int u = s.empty() || *s.rbegin() < x ? inf : *s.lower_bound(x), v = t.empty() || *t.rbegin() < x ? inf : *t.lower_bound(x); if (u == inf && v == inf) { continue; } if (u < v) { s.erase(u); if (--sum[u]) { t.insert(u); } } else { t.erase(v), --sum[v], s.insert(v); } } seq.clear(); for (auto x : s) { seq.pb(x); } s.clear(); for (int i = 0; i < seq.size(); i += 2) { ++sum[seq[i]], t.insert(seq[i]); if (i + 1 < seq.size()) { if (--sum[seq[i + 1]]) { t.insert(seq[i + 1]); } } } for (auto x : all[i]) { if (t.find(x) != t.end()) { t.erase(x); } if (sum[x]++ & 1) { ++sum[x]; } s.insert(x); } } for (int i = 1; i <= m; ++i) { ans += sum[i]; } printf("%d\n", ans); #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }