2022 Usaco US Open银组题解，有哪些解题技巧分享？

本文共计2855个文字，预计阅读时间需要12分钟。

T1+题目简述+有+（n）+只奶牛，第+（i）+只奶牛希望拜访第+（a_i）+只奶牛。给定一个+（1）+到+（N）+的排列+（（p_1，p_2，...，p_n）+），对于从+（1）+到+（n）+的每一个+（i）+：如果奶牛+（a_{p_i}）+已经访问过。

T1

题意简述

• 有 \(n\) 只奶牛，第 \(i\) 只奶牛希望拜访第 \(a_i\) 只奶牛。
• 给定一个 \(1\) . . . \(N\) 的排列 \((p_1, p_2, ..., p_n)\)，对于从 \(1\) 到 \(n\) 的每一个 \(i\)：
  • 如果奶牛 \(a_{p_i}\) 已经离开了她的农场，那么奶牛 \(p_i\) 仍然留在她的农场。
  • 否则，奶牛 \(p_i\) 就会离开她的农场去拜访第 \(a_{p_i}\) 只奶牛，并产生 \(v_{p_i}\) 次快乐的哞叫。
• 给出序列 \(a_n\) 与 \(v_n\)，对于所有可能的排列 \(p\)，计算可能得到的快乐哞叫的次数的最大值。
• \(2 \leq n \leq 10^5\)，\(0 \leq v_i \leq 10^9\)。

解题思路

十分有趣的图论题。

我们建立一个 \(n\) 条边 \(n\) 个点的有向图，第 \(i\) 条边从 \(i\) 连向 \(a_i\)。注意到图不一定连通。

首先考虑对于 \(a_i \neq a_j\) 的部分分如何解决。这种情况下，每个连通块都形成一个简简单单的环。

容易发现最优情况下，应当是先由一头起始奶牛 \(i\) 拜访 \(a_i\)，然后 \(a_i\) 拜访 \(a_{a_i}\)，然后 \(a_{a_i}\) 拜访 \(a_{a_{a_i}}\)，以此类推。

所以这种情况下，每个连通块的答案就是 \(v_i\) 的和减去这个连通块内 \(v_i\) 的最小值。

那么对于非特殊情况，我们如何解决呢？先随意画出一张可能的有向图观察一下吧。

我们发现每一个连通块内有且仅有一个环，那么我们就可以把点分成两类：

• 如果这个点不在环上，我们先让它进行拜访，它一定能对答案产生贡献。（见下图）
• 如果这个点在环上，那么我们用部分分的思路推导，也一定有且仅有一个环上的点无法产生贡献。

问题也就迎刃而解了。我们对于每个连通块，统计所有 \(v_i\) 的和，再减去环上的点的 \(v_i\) 的最小值，就是答案。

代码

#include <bits/stdc++.h> #define int long long using namespace std; inline int read() { int x = 0; char ch = getchar(); while (!isdigit(ch)) ch = getchar(); while (isdigit(ch)) x = (x<<3) + (x<<1) + ch - '0', ch = getchar(); return x; } const int L = 1e5 + 5; int n, ans, minn, a[L], v[L], f[L], in[L]; vector<int> vec, son[L]; bool vis[L]; void get_point(int x) { // 获取每一个连通块中的点 vis[x] = true, vec.push_back(x); for (int i = 0; i < son[x].size(); i++) if (!vis[son[x][i]]) get_point(son[x][i]); if (!vis[a[x]]) get_point(a[x]); } void get_circle(int x) { // dfs 找环，同时直接更新最小值 f[x]++; if (f[x] == 2) minn = min(minn, v[x]); if (f[a[x]] != 2) get_circle(a[x]); } signed main() { n = read(); for (int i = 1; i <= n; i++) a[i] = read(), v[i] = read(), son[a[i]].push_back(i), in[a[i]]++; for (int i = 1; i <= n; i++) { if (vis[i]) continue; minn = L*L; get_point(i); get_circle(i); for (int j = 0; j < vec.size(); j++) ans += v[vec[j]]; ans -= minn; vec.clear(); } printf("%lld", ans); return 0; }

---

T2

题意简述

• 给定两个字符串 \(s\) 和 \(t\)，仅由小写字母 'a' 到 'r' 组成。
• \(q\) 次询问，每次给出一个小写字母 'a' 到 'r' 的子集，你需要判断 \(s\) 与 \(t\) 在删去了不包含在子集内的字符后是否相等，相等输出 'Y'，不相等输出 'N'。每次询问独立。
• \(\mid s \mid, \mid t \mid \leq 10^5\)，\(1 \leq q \leq 10^5\)。

解题思路

首先思考暴力做法：对于每次询问，对两个字符串暴力地扫一遍，剔除不包含在自己内的字符，然后 \(O(n)\) 判断两个字符串是否相等。

时间复杂度达到了 \(O(nq)\)，显然过不去。怎么办呢？

观察题面，注意到本题有一个不同寻常的限制：

仅由小写字母 'a' 到 'r' 组成。

'r' 是字母表里的第 \(18\) 个字母，而所有 'a' 到 'r' 的子集个数只有 \(2^{18} = 262144\)，似乎......不是很大？

考虑使用状压 dp 预处理出答案，我们设询问子集的元素个数为 \(k\)，分类如下：

• 如果 \(k = 1\)，比如 'a'、'b'，我们直接统计这个字符在 \(s\) 与 \(t\) 中出现的次数即可。
• 如果 \(k = 2\)，比如 'ab'、'ac'，我们用暴力方法判断是否相等。
• 如果 \(k \geq 3\)，比如 'abc'、'defg'、'acdfh'，我们发现当且仅当询问子集的所有子集的答案都是 'Y' 的时候询问子集的答案才是 'Y'。为了简化，我们只用判断询问子集的所有元素个数等于 \(k-1\) 的子集即可。

比如，对于样例中的情况，即 $s = $ "\(\texttt{aabcd}\)"，$t = $ "\(\texttt{caabd}\)"：

• 我们观察到两个字符串中 'a'、'b'、'c'、'd' 的数量都相同，所以:
  \(dp[\)'a'\(] = dp[\)'b'\(] = dp[\)'c'\(] = dp[\)'d'\(] = true\)
• 对于子集 'ab'、'ac'、'ad'、'bc'、'bd'、'cd'，我们暴力判断，得出:
  \(dp[\)'ab'\(] = dp[\)'ad'\(] = dp[\)'bd'\(] = dp[\)'cd'\(] = true\)，\(dp[\)'ac'\(] = dp[\)'bc'\(] = true\)
• 对于子集 'abc'，我们发现 \(dp[\)'ab'\(] = true\)，\(dp[\)'ac'\(] = dp[\)'bc'\(] = false\)，不满足它所有子集答案都是 'Y'，所以：
  \(dp[\)'abc'\(] = false\)。
• 而对于子集 'abd'，我们发现 \(dp[\)'ab'\(] = dp[\)'ad'\(] = dp[\)'bd'\(] = true\)，所以 \(dp[\)'abd'\(] = true\)。
• 子集 'acd'、'bcd'、'abcd' 同理。

具体如何实现呢？我们考虑使用二进制的思想将所有 'a' 到 'r' 的子集变为一个数。比如将 'a' 转化为 \(1\)、将 'b' 转化为 \(2\)、将 'c' 转化为 \(4\)、将 'abc' 转化为 \(7\)。

同时，我们预处理出元素个数等于 \(1\) 的子集与元素个数等于 \(2\) 的子集，进行特殊处理。

代码

#include <bits/stdc++.h> using namespace std; inline int read() { int x = 0; char ch = getchar(); while (!isdigit(ch)) ch = getchar(); while (isdigit(ch)) x = (x<<3) + (x<<1) + ch - '0', ch = getchar(); return x; } const int L = (2<<18); int q, x, cnt, f1[L], f2[L], tmp1[L], tmp2[L], cnt1[20], cnt2[20]; string s, t, ask; bool dp[L]; int main() { cin >> s >> t; for (int i = 0; i < s.size(); i++) cnt1[s[i]-'a']++; // 预处理出 s 中每个字符出现的个数 for (int i = 0; i < t.size(); i++) cnt2[t[i]-'a']++; // 预处理出 t 中每个字符出现的个数 for (int i = 0; i <= 17; i++) { // 预处理出元素个数等于 1 的子集与元素个数等于 2 的子集 f1[(1<<i)] = i+1; for (int j = i+1; j <= 17; j++) f1[(1<<i)+(1<<j)] = i+1, f2[(1<<i)+(1<<j)] = j+1; } for (int i = 1; i <= L-1; i++) { if (f1[i] && !f2[i]) { // 元素个数等于 1 的子集 if (cnt1[f1[i]-1] == cnt2[f1[i]-1]) dp[i] = true; else dp[i] = false; } else if (f1[i]) { // 元素个数等于 2 的子集 if (cnt1[f1[i]-1] != cnt2[f1[i]-1] || cnt1[f2[i]-1] != cnt2[f2[i]-1]) dp[i] = false; else { // 暴力判断 cnt = 0; for (int j = 0; j < s.size(); j++) if (s[j]-'a' == f1[i]-1 || s[j]-'a' == f2[i]-1) tmp1[++cnt] = s[j]-'a'; cnt = 0; for (int j = 0; j < t.size(); j++) if (t[j]-'a' == f1[i]-1 || t[j]-'a' == f2[i]-1) tmp2[++cnt] = t[j]-'a'; dp[i] = true; for (int j = 1; j <= cnt; j++) if (tmp1[j] != tmp2[j]) dp[i] = false; } } else { dp[i] = true, x = i; for (int j = 17; j >= 0; j--) { if (x < (1<<j)) continue; x -= (1<<j); if (!dp[i-(1<<j)]) dp[i] = false; } } } q = read(); while (q--) { cin >> ask, x = 0; for (int i = 0; i < ask.size(); i++) x += (1<<(ask[i]-'a')); if (dp[x]) printf("Y"); else printf("N"); } return 0; }

---

T3

题意简述

• 给定一个仅包含字符 'C'，'O' 和 'W' 的字符串 \(s\)，有两种操作：
  1.选择两个相邻的字符并将其删除。
  2.选择一个字母，将其替换为另外两个字母的任一排列。
• \(q\) 次询问，每次询问给定 \(l, r\)，问能否通过上述两种操作将 \(s\) 的子串 \([l, r]\) 变为单个字母 'C'，能则输出 'Y'，不能则输出 'N'。
• \(1 \leq l \leq r \leq \mid s \mid \leq 2 \cdot 10^5\)， \(1 \leq q \leq 2 \cdot 10^5\)。

解题思路

比较简单的思维题。

首先思考在变化的字符串 \(s\) 中有什么是不变的。

这种题目的一个常见套路就是分析奇偶性。我们记字符 'C'，'O'，'W' 的个数为 \(c, o, w\)，列出下表观察奇偶性：

\(c\) \(o\) \(w\) \(c+o\) \(o+w\) \(w+c\) \(c+o+w\) 操作 \(1\) 奇偶性不变 奇偶性不变 奇偶性不变 奇偶性不变 奇偶性不变 奇偶性不变 奇偶性不变 操作 \(2\) 奇偶性变 奇偶性变 奇偶性变 奇偶性不变 奇偶性不变 奇偶性不变 奇偶性变

我们惊奇地发现：\(c+o, o+w, w+c\) 的奇偶性自始至终都不变！

既然我们需要把字符串变成单个字符 'C'，那么 \(c+o\) 就 \(w+c\) 就应该是奇数，\(o+w\) 就应该是偶数。

那么解法也呼之欲出了。我们使用前缀和维护 'c'，'o'，'w' 出现的次数，对于每一次询问，求出该子串里 \(c+o, o+w, w+c\) 的值，再判断奇偶性是否符合要求即可。

代码

#include <bits/stdc++.h> using namespace std; inline int read() { int x = 0; char ch = getchar(); while (!isdigit(ch)) ch = getchar(); while (isdigit(ch)) x = (x<<3) + (x<<1) + ch - '0', ch = getchar(); return x; } const int L = 2e5 + 5; int q, l, r, c, o, w, pre[L][3]; string s; int main() { cin >> s; for (int i = 0; i < s.size(); i++) { if (i) pre[i][0] = pre[i-1][0], pre[i][1] = pre[i-1][1], pre[i][2] = pre[i-1][2]; if (s[i] == 'C') pre[i][0]++; else if (s[i] == 'O') pre[i][1]++; else pre[i][2]++; } q = read(); while (q--) { l = read()-1, r = read()-1; if (l) c = pre[r][0]-pre[l-1][0], o = pre[r][1]-pre[l-1][1], w = pre[r][2]-pre[l-1][2]; else c = pre[r][0], o = pre[r][1], w = pre[r][2]; if (((c+o)&1) && ((c+w)&1) && !((o+w)&1)) printf("Y"); else printf("N"); } return 0; }