2022ICPC杭州-K,A,C,G,M个人题解如何获取？

K - Master of Both trie #逆序对 #字符串 问题描述 灰机教授是字符串宗师与高级数据结构师，这天他想到了这样一个问题：按顺序给定 \(n\) 个仅包含小写字母的字符串，按照字典序，这些串当中有几个逆序对？ 按照字典序来处理，这个问题并不困难；然而，在 \(q\) 个不同的平行世界中，字典序并不像我们现在所处的世界这样规定。 准确来说，每个平行宇宙的字母表都是一个长度为 \(26\) 的包含了每一种小写字母的串，表示字母之间的顺序关系。 我们称 \(a\) 的字典序小于 \(b\) 当且仅当满足以下条件之一： \(a\) 是 \(b\) 的前缀，但 \(a \neq b\)； 在 \(a\) 与 \(b\) 对应字符不同的第一个位置上，字符串 \(a\) 在这个位置上的字符在字母表中出现的位置早于字符串 \(b\) 的。 一个长度为 \(n\) 的序列 \(a\) 的逆序对数是满足 \(1 \leq i < j \leq n\)，\(a_j < a_i\) 的 \((i,j)\) 的数目。 思路 由于每次询问的字典序都不一样，所以我们需要记录由\(abcd\dots z\)这\(26\times 26\)对有序对构成的逆序对的数量，这样就可以在不同的字典序时\(26^{2}\)的复杂度枚举所有字母有序对，根据他们的数量以及字典序来计算逆序对 创建一个二维数组\(mp[27][27]\)，其中\(mp[c_{1}][c_{2}]\)用于记录逆序对\(<c_{1},c_{2}>\)的个数 想要计算字符串之间的逆序对，需要将字符串一一插入trie树中 插入的过程中，当前节点\(c_{1}\)的兄弟节点\(c_{2}\)的权值即为逆序对\(<c_{1},c_{2}>\)的新增数量，因此\(mp[c_{1}][c_{2}]+=cnt[c_{2}]\) 为了计算“当前字符串属于已插入字符串的前缀”的情况，在插入过程的最后一个节点\(c\)，答案需要加上\(delta=\sum cnt[c_{son}]\)（此偏移量直接作用于最后的\(ans\)输出） 代码 #include<bits/stdc++.h> using namespace std; #define ll long long #define int ll #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define endl '\n' int mp[27][27]; const int N = 1e6 + 5; int ch[N][27], cnt[N], idx, del; int getnum(char s) { return s - 'a'; } void insert(string& s) { int len = s.length() - 1, p = 0; rep(i, 0, len) { int j = getnum(s[i]); if (!ch[p][j])ch[p][j] = ++idx; rep(k, 0, 25) { if (k == j)continue; mp[j][k] += cnt[ch[p][k]]; } p = ch[p][j]; cnt[p]++; } rep(k, 0, 25) { del += cnt[ch[p][k]]; } } void solve() { int n, q;cin >> n >> q; rep(i, 1, n) { string s;cin >> s; insert(s); } rep(i, 1, q) { string s;cin >> s; int ans = 0; vector<int>id(27); rep(i, 0, 25) { id[s[i] - 'a'] = i; } rep(x, 0, 25) { rep(y, 0, 25) { if (x == y)continue; int v1 = id[x], v2 = id[y]; if (v1 < v2)ans += mp[x][y];//x<y } } cout << ans + del << '\n'; } } signed main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int t = 1; // cin >> t; while (t--)solve(); } A - Modulo Ruins the Legend 数学 #同余 #exgcd #数论 题目描述 格莱米有一个整数序列 a1, a2, . . . , an。她认为序列中的元素太大了，因此她决定给序列加上一个等差数列。具体来说，她可以选择两个非负整数 \(s\) 和 \(d\)，然后对每个 \(k ∈ [1, n]\)，将 \(a_k\) 加上 \(s + kd\)。 由于我们想要打破这个传说，请告诉她操作后元素和模 \(m\) 的最小值。注意，你需要在取模后最小化这个和。 思路 很容易推导得到，需要： \[(A+Bs+Cd)\%m=x \] 求解令\(x\)最小的\(s\)与\(d\)。 \[\begin{align} (Bs+Cd)\%m&=(x-A)\%m\\ \\ Bs+Cd&=k_{1}m+x-A \end{align} \] 由\(exgcd\)有解的结论可知： \[\begin{align} &k_{1}m+x-A=k_{2}gcd(B,C)\\ \\ &记g_{1}=gcd(B,C)\\ \\ \implies&x-A=-mk_{1}+g_{1}k_{2}=mk_{1}+g_{1}k_{2} \end{align} \] 由\(exgcd\)有解的结论可知： \[\begin{align} &x-A=k_{0}gcd(m,g_{1})\\ \\ &记g_{2}=gcd(m,g_{1})\\ \\ \implies&x=A+k_{0}g_{2}>0\\ \\ \implies&当k_{0}=-\left\lceil \frac{A}{g_{2}} \right\rceil时x最小\\ \\ \implies&x=A-\left\lceil \frac{A}{g_{2}} \right\rceil g_{2} \end{align} \] 随后一路使用\(exgcd\)反解方程即可 特别要注意解方程得到的结果需要对\(m\)取模，因为本题的所有运算都是在模\(m\)的意义下进行的 代码 #include<bits/stdc++.h> using namespace std; #define ll long long #define int ll #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) // #define endl '\n' int lcm(int x, int y) { return x * y / __gcd(x, y); } void exgcd(int a, int b, int& x, int& y) { if (b == 0) { x = 1, y = 0; return; } exgcd(b, a % b, y, x); y -= a / b * x; } void solve() { int n, m;cin >> n >> m; int sum = 0; rep(i, 1, n) { int x;cin >> x;sum += x; } int A = sum % m, B = n % m, C = (n * (n + 1) / 2) % m; int g1 = __gcd(B, C), g2 = __gcd(m, g1); int x = ceil(-1.0 * A / g2) * g2 + A; int k0 = (x - A) / g2; k0 = (k0 % m + m) % m; int x0 = 0, y0 = 0; exgcd(m, g1, x0, y0); int k1 = k0 * x0, k2 = y0 * k0; k1 = (k1 % m + m) % m; k2 = (k2 % m + m) % m; int s0 = 0, d0 = 0; exgcd(B, C, s0, d0); int s = k2 * s0; int d = k2 * d0; s = (s % m + m) % m; d = (d % m + m) % m; cout << x << '\n' << s << " " << d << '\n'; } signed main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int t = 1; // cin >> t; while (t--)solve(); } C - No Bug No Game dp #背包dp 题目描述 在希伯来大学，学生们正在参与一场校园游戏，游戏内容是为自己装备 \(n\) 件科技物品以提升分数。每件物品有一个基础能力值 \(p_i\)，并且可以通过一种特殊的全校增益效果进行强化。 这个增益效果是有限的——它最多能升级总计 \(k\) 点基础能力值。物品按照选定的顺序一件一件地装备。当处理每件物品 \(i\) 时，游戏系统会检查已扫描物品的总基础能力值，记为 \(sum = \sum_{j=1}^{i-1} p_j\)： 如果 \(sum + p_i \le k\)，则该物品被完全升级，并增加 \(w_{i, p_i}\) 点奖励能力值。 如果 \(sum \ge k\)，则该物品完全不被升级。 否则，该物品被部分升级，并增加 \(w_{i, k - sum}\) 点奖励能力值。 学生们希望选择最佳的装备顺序，以最大化总奖励能力值。你能帮助他们吗？ 注意：这个增益系统有些特殊——即使 \(a < b\)，也可能出现 \(w_{i, a} > w_{i, b}\) 的情况。 思路 由于当 \(sum \ge k\)的时候物品不会给答案有贡献，所以只分两种情况，第一种是还没有出现转折点的时候，第二种是已经出现了转折点 状态设计： \(dp[i][sum][0/1]\)表示当前正在决策第\(i\)个物品，前缀和为\(sum\)，0表示没有出现转折点，1表示已经出现了转折点，\(dp\)的值代表最大的能量值 第一维度可以用滚动数组省去 状态转移： 先枚举决策的物品\(i\)，再枚举当前的前缀和\(V\)（类比背包dp的空间） 尝试将当前物品作为转折点： 枚举\(add=k-sum\)：\(chmax(ndp[V + add][1], dp[V][0] + w[i][add])\) 尝试对当前物品的选择与否进行转移：\(chmax(ndp[V + p[i]][0], dp[V][0] + w[i][p[i]])\) 代码 #include<bits/stdc++.h> using namespace std; #define ll long long #define int ll #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) void chmax(int& x, int y) { x = max(x, y); } const int inf = 2e14; void solve() { int n, k;cin >> n >> k; vector<vector<int>>w(n + 1); vector<int>p(n + 1); rep(i, 1, n) { cin >> p[i]; w[i].resize(p[i] + 1); rep(j, 1, p[i]) { cin >> w[i][j]; } } vector<array<int, 2>>dp; rep(i, 0, 1)dp.resize(k + 1, array<int, 2>({ -inf,-inf })); dp[0][0] = 0; rep(i, 1, n) { auto ndp = dp; rep(V, 0, k) { rep(add, 1, p[i]) { if (V + add > k)break; chmax(ndp[V + add][1], dp[V][0] + w[i][add]); } if (V + p[i] <= k)chmax(ndp[V + p[i]][1], dp[V][1] + w[i][p[i]]); if (V + p[i] <= k)chmax(ndp[V + p[i]][0], dp[V][0] + w[i][p[i]]); } dp = ndp; } int ans = 0; rep(V, 0, k) { chmax(ans, dp[V][0]); } chmax(ans, dp[k][1]); cout << ans << '\n'; } signed main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int t = 1; // cin >> t; while (t--)solve(); } G - Subgraph Isomorphism 树同构 #树哈希 #基环树 题目描述 格莱米想要获得图灵奖！她决定尝试在多项式时间内解决子图同构问题。 由于这个问题确实太难了，她决定先进行一些简化，尝试解决简化后的问题。 现在，格莱米有一个连通的无向图 \(G\)，包含 \(n\) 个顶点和 \(m\) 条边。她想知道，是否能找到一棵具有 \(n\) 个顶点的树 \(T\)，使得 \(G\) 中所有具有 \(n\) 个顶点和 \(n-1\) 条边的连通子图都与 \(T\) 同构。格莱米当然知道答案，但她想考考你。 两个图 \(G\) 和 \(H\) 同构当且仅当存在一个从 \(G\) 的顶点集到 \(H\) 的顶点集的双射（\(f : V(G) \rightarrow V(H)\)），使得 \(G\) 中的任意两个顶点 \(u\) 和 \(v\) 在 \(G\) 中相邻当且仅当 \(f(u)\) 和 \(f(v)\) 在 \(H\) 中相邻。 两个顶点相邻当且仅当它们由一条边直接相连。 思路 首先根据树同构的定义，当\(m=n-1\)的时候，自己和自己肯定同构，输出yes 如果存在一棵树能够使得任意生成树都与他同构，那么一定只能有一个环，是一棵基环树。 将环上的每个点看作一个个根节点，则有很多棵树挂在环上。类似高中化学的苯环，满足题意的结构必须具有高度对称性。 如果\(m>n\)，那么一定至少有2个环，此时必定不能任意生成树同构。 如果环上的树结构为\(AAAA\dots A\)那么显然各个方向都对称 如果环上的树的结构为\(ABABA\dots ABA\)那么环的长度必须为偶数的时候才有可能从各个方向看都对称 最后对每个根节点跑一遍树哈希的板子，算出每棵树的哈希值，即可判断结构是否合法了 代码 #include<iostream> #include<vector> #include<random> #include<queue> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define ll long long const int N = 1e5 + 5; vector<int>e[N]; int deg[N]; #define ull unsigned long long const ull P = mt19937_64(time(0))(); ull shift(ull x) { x ^= P; x ^= x << 13; x ^= x >> 7; x ^= x << 17; x ^= P; return x; } ull h[N]; vector<int>vis; void dfs(int u, int fa) { // cout << "u,fa:" << u << " " << fa << endl; h[u] = 1; for (auto& son : e[u]) { if (son == fa || !vis[son] || vis[son] == 2)continue; dfs(son, u); h[u] += shift(h[son]); } } void solve() { int n, m; cin >> n >> m; vis.assign(n + 1, 0); rep(i, 1, n) { e[i].clear(); deg[i] = 0; } rep(i, 1, m) { int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); deg[u]++, deg[v]++; } if (m == n - 1) { cout << "YES\n"; return; } if (m > n) { cout << "NO\n"; return; } deque<int>dq; rep(i, 1, n)if (deg[i] == 1)dq.push_back(i); while (dq.size()) { auto u = dq.front(); dq.pop_front(); vis[u] = 1; for (auto& son : e[u]) { if (vis[son])continue; deg[son]--; if (deg[son] == 1)dq.push_front(son); } } int cnt = 0, st; rep(i, 1, n) { if (vis[i] == 0) { st = i; break; } } int pos = st; vector<int>id(1, 0); while (1) { // cout << "pos:" << pos << endl; vis[pos] = 2; dfs(pos, 0); id.push_back(pos); int tmp = pos; // cout << "cnt id:" << cnt << " " << id[cnt] << endl; for (auto& son : e[pos]) { if (vis[son] == 0) { pos = son; break; } } if (pos == tmp)break; } bool flag1 = 1, flag2 = 1; rep(i, 2, id.size() - 1) { if (h[id[i]] != h[id[i - 1]]) { flag1 = 0; break; } } rep(i, 3, id.size() - 1) { if (h[id[i]] != h[id[i - 2]]) { flag2 = 0; break; } } if ((id.size() - 1) % 2)flag2 = 0; if (flag1 || flag2)cout << "YES\n"; else cout << "NO\n"; } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--)solve(); } M - Please Save Pigeland 一种名为神秘奥斯卡的可怕疾病正在猪猪国传播。猪猪国有 \(n\) 个城市，由 \(n-1\) 条双向道路连接。第 \(i\) 条道路连接城市 \(u_i\) 和城市 \(v_i\)，长度为 \(w_i\)。保证任意一个城市都可以通过这些道路到达任何其他城市。 现在，有 \(k\) 个不同的城市 \(c_1, c_2, \dots, c_k\) 患有这种可怕的疾病。作为猪猪国的领袖，Putata 和 Budada 将要拯救猪猪国。首先，他们会找一个城市 \(r\) 建立医院，不考虑城市 \(r\) 是否被疾病感染。然后，他们会用剩下的钱建造唯一一种可以在猪猪国行驶的交通工具——猪猪车。由于资金紧张，他们只能建造一辆猪猪车，而且一旦猪猪车建造完成，其某个参数 \(d\) 就被设定，无法更改。具有参数 \(d\) 的猪猪车只能从一个城市前往另一个城市，且两个城市之间的最短距离必须是 \(d\) 的倍数。形式上，如果你想从城市 \(u\) 前往城市 \(v\)，\(u\) 和 \(v\) 之间的最短路径长度应为 \(p \times d\)，其中 \(p\) 是非负整数，并且这将花费 \(p\) 猪猪币。请注意，如果你想从城市 \(u\) 前往城市 \(v\)，并不需要在 \(u\) 到 \(v\) 路径上的每个城市停留，只要 \(u\) 和 \(v\) 之间的最小距离是 \(d\) 的倍数，猪猪车就可以直接从一个城市到另一个城市。 在接下来的 \(k\) 天里，Putata 和 Budada 将采取以下行动来拯救猪猪国。在第 \(i\) 天，他们将乘坐猪猪车从城市 \(r\) 出发，沿着城市 \(r\) 到城市 \(c_i\) 的最短路径前往城市 \(c_i\)，治愈该城市的所有猪猪，然后从城市 \(c_i\) 返回城市 \(r\)。 Putata 和 Budada 希望您选择合适的城市 \(r\) 建立医院，以及他们应该建造的猪猪车参数 \(d\)，以使得旅行期间花费的猪猪币最小。请帮助他们找出花费的最小猪猪币数量。 思路 首先，考虑固定树根\(r\)的情况： 显然，参数\(d\)必定是所有\(c\)城市到达根部距离的\(gcd\) 答案即为所有城市到根部距离之和除以\(gcd\) 由于需要求\(r\)在所有节点时的情况并取最小值，显然这是一个换根dp问题，所以考虑如何转移： 记\(siz[u]\)为\(u\)的子树大小 记\(cnt[u]\)为\(u\)的子树内有多少个\(c\)城市 记\(d[u]\)为\(u\)到\(1\)结点的距离 则第一遍\(dfs\)可以预处理出上述信息 记\(sum[u]\)为以\(u\)作为根节点\(r\)时，所有\(c\)城市到达\(u\)的距离之和，将根从\(u\)转移到\(son\)时，\(son\)子树内的\(c\)城市距离都要减少边权\(w\)，不在\(son\)子树内的\(c\)城市都要加上\(w\)，即： \[sum[son]=sum[u]-cnt[son]\times w+(k-cnt[son])\times w \] 处理完距离和的转移，接下来要处理\(gcd\)： 记\(dfn[u]\)为\(u\)的\(dfs\)序时间戳 记\(T[i]\)为第\(i\)个\(c\)城市被遍历的时间 将\(k\)个城市的距离\(d\)储存到新的数组\(a[N]\)中，其差分数组记为\(b[N]\) 创建一棵线段树维护差分数组的\(gcd\) \[gcd(a_{1},a_{2},a_{3},\dots,a_{n})=gcd(a_{1},a_{2}-a_{1},a_{3}-a_{2},\dots,a_{n}-a_{n-1})=gcd(b_{1},b_{2},b_{3}\dots,b_{n}) \] 注意在处理\(gcd\)的时候必须要保证非负 将根从\(u\)转移到\(son\)时，\(son\)子树内的\(c\)城市距离都要减少边权\(w\)，只需要修改差分数组上的两个点即可，不在\(son\)子树内的\(c\)城市都要加上\(w\)，给差分数组修改两个点即可，状态更新的时候一定要注意对边界分类 在\(T\)数组上二分即可找到当前子树所对应的范围\(l,r\) 代码 #include<bits/stdc++.h> using namespace std; #define ll long long #define int ll #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) const int N = 5e5 + 5; int n, k; vector<pair<int, int>>e[N]; int d[N], tag[N], cnt[N], sum[N], siz[N]; int a[N], b[N], tim, dfn[N]; int gcd(int x, int y) { return __gcd(abs(x), abs(y)); } int nn, T[N]; void dfs(int u, int fa) { tim++; if (tag[u]) { a[++nn] = d[u]; T[nn] = tim; } dfn[u] = tim; siz[u] = 1; if (tag[u])cnt[u] = 1; for (auto [w, son] : e[u]) { if (son == fa)continue; d[son] = d[u] + w; if (tag[son])sum[1] += d[son]; dfs(son, u); cnt[u] += cnt[son]; siz[u] += siz[son]; } //cout << "u,cnt[u],head[u],g[u]:" << u << " " << cnt[u] << " " << head[u] << " " << g[u] << endl; } int G[N << 2]; #define ls p<<1 #define rs p<<1|1 #define mid (l+r>>1) void pushup(int p) { G[p] = gcd(G[ls], G[rs]); } int query_G(int p, int l, int r, int x, int y) { if (l > r)return 0; if (x <= l && r <= y)return G[p]; int res = 0; if (x <= mid)res = gcd(res, query_G(ls, l, mid, x, y)); if (y > mid)res = gcd(res, query_G(rs, mid + 1, r, x, y)); return res; } void update(int p, int l, int r, int pos, int val) { if (l > r)return; if (l == r) { b[l] += val;G[p] = abs(b[l]); return; } if (pos <= mid)update(ls, l, mid, pos, val); else update(rs, mid + 1, r, pos, val); pushup(p); } void build(int p, int l, int r) { G[p] = abs(b[l]); if (l == r)return; build(ls, l, mid), build(rs, mid + 1, r); pushup(p); } int ans; void dfs2(int u, int fa) { // cout << "u,fa:" << u << " " << fa << endl; for (auto [w, son] : e[u]) { if (son == fa)continue; // cout << "son:" << son << '\n'; sum[son] = sum[u] - cnt[son] * w + (k - cnt[son]) * w; int l = lower_bound(T + 1, T + 1 + nn, dfn[son]) - T; int r = upper_bound(T + 1, T + 1 + nn, siz[son] + dfn[son] - 1) - T - 1; if (l <= r) { if (l == 1)update(1, 1, nn, 1, -w); else update(1, 1, nn, 1, w); if (l > 1)update(1, 1, nn, l, -2 * w); if (r < nn)update(1, 1, nn, r + 1, 2 * w); } else { update(1, 1, nn, 1, w); } int res = 0; if (G[1] != 0)res = sum[son] / G[1]; res = max(res, 0ll); ans = min(ans, res); dfs2(son, u); if (l <= r) { if (l == 1)update(1, 1, nn, 1, w); else update(1, 1, nn, 1, -w); if (l > 1)update(1, 1, nn, l, 2 * w); if (r < nn)update(1, 1, nn, r + 1, -2 * w); } else { update(1, 1, nn, 1, -w); } } } void solve() { cin >> n >> k; rep(i, 1, k) { int x;cin >> x; tag[x] = 1; } rep(i, 1, n - 1) { int u, v, w;cin >> u >> v >> w; e[u].push_back({ w,v }); e[v].push_back({ w,u }); } dfs(1, 0); rep(i, 1, nn)b[i] = a[i] - a[i - 1]; build(1, 1, nn); if (G[1] != 0)ans = sum[1] / G[1]; ans = max(ans, 0ll); dfs2(1, 0); cout << ans * 2 << '\n'; } signed main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int t = 1; //cin >> t; while (t--)solve(); }