文章转载自奇点编程，版权归原作者所有
大家好，USACO试题解析系列又和大家见面啦！截至北京时间本周二晚，USACO 本赛季最后一场比赛已结束，后续就是Training Camp。满分同学会当场晋级，没有当场晋级的同学可以耐心等待一周之内出成绩。
打完本场比赛，不少考铜级的同学会觉得本次铜级难度又被拉爆了，得满分很有挑战性。没有简单题，只有难题和更难的题，铜级命题者这次清一色华人，果然是华人卷死华人不偿命。本次银级难度还算相对平稳。本次金级和铂金级难度相比较上个月有较大提升。 所以不要把晋级的希望全部寄托在某一场比赛中，多参赛几回，才会有更大的晋级概率！
推荐各位同学认真读一读题解，把握一下比赛难度的变化趋势。
更多内容，请参考下文解析。
大家的眼睛是雪亮的，成绩不是靠口头喊出来的，而是需要一步一步长期耕耘才能结出硕果。能够在官方题解公布之前，原创全部组别题解的机构，是真硬核！
（需要转载的请注明来源，尊重他人劳动成果）
以下内容是各大级别的赛题解析，供同学们参考交流。想要咨询参赛和备考冲刺计划的同学，可以扫描文末二维码，添加老师微信获取。
第1题
题目解析：
第一题主要就是找规律，观察多个连续的F如何变化，发现如果在中间要么会变成全是奇数，要么全是偶数，在边上就是连续的整数。分情况讨论就行。完整代码如下：
using namespace std;char s[200010];int main() { int n; cin >> n; if (n == 1) { cout << 0; return 0; } // l和r之间都为F int l = -1, r = -1, d = 0, u = 0, isc = 1; cin >> s; for (int i = 0; i < n; i++) { if (s[i] == 'F') { if (i == 0) l = -1; else if (s[i - 1] != 'F') l = i - 1;
if (i == n - 1) { // 末尾是F isc = 0; if (l == -1) u += n - 1; else u += i - l; } else if (s[i + 1] != 'F') { r = i + 1; if (l == -1) { isc = 0; u += r; } else if (s[r] == s[l]) { u += r - l; d += (r - l) % 2; } else { u += r - l - 1; d += (r - l - 1) % 2; } } } if (i > 0) { if (s[i] != 'F' && s[i] == s[i - 1]) { // 相邻两个字符一样，最大最小值各加1 u++; d++; } } }
if (isc) { // F都在中间 cout << (u - d) / 2 + 1 << endl; for (int i = d; i <= u; i += 2) cout << i << 'n'; } else { cout << (u - d) + 1 << endl; for (int i = d; i <= u; i += 1) cout << i << 'n'; }}第2题
题目解析：
本题题意不难理解，细节比较多，属于复杂的枚举题。要枚举不同词性的单词之间的各种组合，细节见代码注释。
完整代码如下：
using namespace std;vector<string> iverb, tverb, noun, con;
int main() { int T; cin >> T; while (T--) { int n, c, p; cin >> n >> c >> p; string s1, s2; string ans = ""; iverb.clear(); // intransitive-verb tverb.clear(); // transitive-verb noun.clear(); // noun con.clear(); // conjunction for (int i = 0; i < n; i++) { cin >> s1 >> s2; if (s2[0] == 'i') iverb.push_back(s1); else if (s2[0] == 't') tverb.push_back(s1); else if (s2[0] == 'n') noun.push_back(s1); else con.push_back(s1); } int ivcnt = iverb.size(); int tvcnt = tverb.size(); int nocnt = noun.size(); int cocnt = con.size();
int ivcnt2 = 0, tvcnt2 = 0, nocnt2 = 0, cocnt2 = 0; int wordcnt = 0;
for (int i = 0; i <= ivcnt; i++) // 枚举用i个intransitive verb for (int j = 0; j <= tvcnt; j++) { // 用j个transitive-verb if (i + j > p + min(cocnt, p)) continue; // 每个verb都要算一句话，一个conjunction可以连接两句话 // conjunction数量要小于等于periods if (i + j * 2 > noun.size()) continue; // int-veb要用一个noun, t-verb至少两个noun，不够就continue int cnt = i * 2 + j * 3 + min((i + j) / 2, cocnt); if (j > 0) { cnt += min(nocnt - i - j * 2, c); // 加上comma的贡献 } if (cnt > wordcnt) { ivcnt2 = i; tvcnt2 = j; if (j > 0) nocnt2 = i + j * 2 + min(nocnt - i - j * 2, c); else nocnt2 = i; cocnt2 = min((i + j) / 2, cocnt); wordcnt = cnt; } } cout << wordcnt << endl;
ivcnt = ivcnt2; tvcnt = tvcnt2; nocnt = nocnt2; cocnt = cocnt2;
int coid = 0, finished = 0; for (int i = 0; i < ivcnt; i++) { ans += noun[i]; ans += ' '; ans += iverb[i]; // 拼接 conjunction if (coid < cocnt && finished == 0) { ans += ' ' + con[coid] + ' '; coid++; finished = 1; // 一句话中最多用一个conjunction } else { ans += ". "; finished = 0; } }
int noid = ivcnt; for (int i = 0; i < tvcnt; i++) { ans += noun[noid]; noid++; ans += ' '; ans += tverb[i]; ans += ' '; ans += noun[noid]; noid++; // 拼接 comma + noun if (i == tvcnt - 1) { while (noid < nocnt) { ans += ", " + noun[noid]; noid++; } }
// 拼接 conjunction if (coid < cocnt && finished == 0) { ans += ' ' + con[coid] + ' '; coid++; finished = 1; } else { ans += ". "; finished = 0; } } if (ans.length() > 0) cout << ans.substr(0, ans.length() - 1) << endl; // 减1是去掉行末空格 else cout << ans << endl; }}第3题
题目解析：
本题直接暴力模拟的话可以对 7/13。想要得满分，得用O(n)的算法来解决。计算每个数字在t的时间内可以动几次，这就是round，而每次动的步数取决于原来位于这个数之前的一开始就能动的数的位置，看该位置动的时候 每次走多远的跨度，那么等下次轮到这个数，也是走这么远。
完整代码如下：
using namespace std;const int N = 2e5 + 1;int n, k, t;int a[N], f[N], p2[N];int main() { cin >> n >> k >> t; for (int i = 1; i <= k; i++) { cin >> a[i]; } a[k + 1] = a[1] + n; for (int i = 1; i <= k; i++) { // f[i]存储数组a的第i个和第(i+1)个元素之间的距离。 f[a[i]] = a[i + 1] - a[i]; } // 往答案数组里填数据 int lst = 0; // 循环遍历n个值，并为每个值计算p2中相应值的索引。 for (int i = 0; i < n; i++) { if (f[i]) lst = i; // 计算t1的值，它是当前索引i被处理后的剩余时间。处理当前索引所花费的时间是(i-lst)。 int t1 = t - (i - lst); // 计算在剩余时间t1内可以完成的距离f[lst]的完整循环数。 int round = ceil(1.0 * t1 / f[lst]); // 使用公式(i+k*f[lst])%n计算出p2中对应值的索引，并设置为i。 p2[(i + round * f[lst]) % n] = i; } cout << p2[0]; for (int i = 1; i < n; i++) { cout << " " << p2[i]; }}
第1题
题目解析
用map和set找到新的位置，然后中间被跳过的依次排名前移或者后移一位，找到这些用前缀和统计就行。
完整代码如下：
using namespace std;int num[200010], sn[200010];long long sum[200010];map<int, int> mp;set<int> s;int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { scanf("%d", &num[i]); sn[i] = num[i]; s.insert(num[i]); } sort(sn + 1, sn + n + 1); long long ans = 0; for (int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + sn[i]; ans += sn[i] * 1ll * i; } for (int i = n; i >= 1; i--) mp[sn[i]] = i; mp[100000001] = n + 1; s.insert(100000001); int q; cin >> q; while (q--) { int t1, t2; scanf("%d%d", &t1, &t2); int a = mp[num[t1]], b = mp[(*s.upper_bound(t2))] - 1; if (a <= b) printf("%lldn", ans - (sum[b] - sum[a]) - num[t1] * 1ll * a + t2 * 1ll * b); else printf("%lldn", ans + (sum[a - 1] - sum[b]) - num[t1] * 1ll * a + t2 * 1ll * (b + 1)); }}第2题
题目解析：
把要找的按前9位分类，后9位预处理，每次枚举所有的前9位。
完整代码如下：
using namespace std;char s[20];int num[100010];int dis[600][600];int h[600];int main() { int n, c; cin >> c >> n; for (int i = 0; i < 512; i++) { int j = i; while (j) { if (j % 2 == 1) h[i]++; j /= 2; } } for (int i = 1; i <= n; i++) { scanf("%s", s); int t = 0; for (int j = 0; j < c; j++) if (s[j] == 'G') t = t * 2; else t = t * 2 + 1; num[i] = t; } for (int i = 0; i < 512; i++) for (int j = 0; j < 512; j++) dis[i][j] = -1e9;
for (int i = 1; i <= n; i++) { int a = num[i] / 512, b = num[i] % 512; for (int j = 0; j < 512; j++) dis[a][j] = max(dis[a][j], h[b ^ j]); }
for (int i = 1; i <= n; i++) { int ans = 0, a = num[i] / 512, b = num[i] % 512; for (int j = 0; j < 512; j++) ans = max(ans, h[a ^ j] + dis[j][b]); printf("%dn", ans); }}
第3题
题目解析：
找到所有的bessie子序列，看有多少个起点会走到。
核心代码如下：
using namespace std;char s[3001];int nex[3001][30];int now[3001];int main() { scanf("%s", s); int l = strlen(s); int t = 0, p = 0; unsigned long long ans = 0; for (int i = 0; i < 26; i++) nex[l][i] = nex[l - 1][i] = l; for (int i = l - 1; i > 0; i--) { for (int j = 0; j < 26; j++) nex[i - 1][j] = nex[i][j]; nex[i - 1][s[i] - 'a'] = i; }
if (s[0] == 'b') now[0] = 1; else if (nex[0]['b' - 'a'] != l) now[nex[0]['b' - 'a']] = nex[0]['b' - 'a'] + 1; for (int i = 0; i < l; i++) if (s[i] == 'b') { int t = nex[i]['e' - 'a']; t = nex[t]['s' - 'a']; t = nex[t]['s' - 'a']; t = nex[t]['i' - 'a']; t = nex[t]['e' - 'a']; if (t != l) { ans += (l - t) * 1ll * now[i]; } if (nex[t]['b' - 'a'] != l) { now[nex[t]['b' - 'a']] += now[i]; } if (nex[i]['b' - 'a'] != l) now[nex[i]['b' - 'a']] += (nex[i]['b' - 'a'] - i); } cout << ans;}
第1题
题目解析：
从起点出发做2次BFS
第一次从1号点到尽可能多的点
第二次考虑如何从所有钥匙都拿起的状态，倒着把钥匙放到应该放的位置。
第一次只考虑c和s, 如果到了一个位置i，但还没有c[i]颜色的钥匙，那么把位置i存在一个 vector<int> b[i]中,一旦拿到c[i]颜色的钥匙，把vector<int> b[i]中所有格子都加入队列。
第二次只考虑c和f, 和第一次的区别在于如果想去一个位置i，当前没有c[i]的钥匙，如果c[i]==s[i]，在第一次中，不能去i。如果c[i]==f[i]，在第二次中，可以去i（倒过来就是先在i放下钥匙，再退回起点）。第二次只能去第一次能到的点（最后一个样例），可能存在一些点去不了，也完全不需要去。
第2题
题目解析：
首先问最多几个bessie非常简单，直接贪心即可，假设答案是z。
接下来问题变成了确认最终会留下z个bessie，问删除哪些字母代价最小。
如果bessie的所有字母均不相同，那么有非常重要的性质：每一个字母如果出现在最终答案中，那么位置是确定的。
现在有重复字母，性质弱了一些，如果一个字母在最终答案中是第x个bessie的第y个字母（如果没有重复字母不需要强调第y个，在这里有2个s和2个e）
那么这个字母在最终答案中不可能成为第非x个的第y个字母。
所以动态规划状态是f[i][j]如果s[i]是bessie的第j个字母，那么最小代价是什么（这里如果确定了s[i]是bessie的第j个字母，那么i之前出现过几次bessie，i之后还需要出现几次bessie都是确定的）
如果j是0，题目不要求不同的bessie之间需要连续，转移就是b[k][5] -> b[i][0]，这样转移不需要删掉k+1到i-1之间的所有字母，不需要额外代价；
如果j非0，转移就是b[k][j-1] -> b[i][j]，这样转移需要删掉k+1到i-1之间的所有字母。转移方程是
f[i][j] = min(f[i][j], f[k][j-1]+b[i]-b[k+1])
f[i][j] = min(f[k][j-1]-b[k+1]) + b[i] 可以提出b[i]
第3题
题目解析：
题目保证有解，注意到无论如何合并，所有点的深度都不可能改变
第一步找到根节点r，然后考虑r的孩子之间是如何合并的。
把final tree建出来，r的一些孩子出现在final tree上，一些孩子没有出现在final tree上
对于没有出现在final tree上的孩子child，考虑他的所有后代是否出现在final tree上
如果存在一个后代出现在final tree上，那么看看这个后代在child的深度是哪个节点，设为tmp。把child合并到tmp下（显然应该有child<tmp，否则无解）
如果不存在任何后代出现在final tree上，那么说明当前树child完完全全被另一个树tmp覆盖了（注意另一个树tmp可能是两个树合成的结果，只出现在final tree中而不在initial tree中），即在任意深度上，child的所有节点都小于另一个树tmp在该深度的最大节点。这一步需要枚举所有在final tree上的孩子，确认是哪一个（直接选择 最大/最深 都是是错误的，任意深度，每一层都要满足）。处理完根节点之后，递归处理final tree的所有孩子。
第1题
限于篇幅，Platinum题目就不贴了
题目解析：
线段树
维护 l r c s 四种数组，每种数组维护 f[6][6] g[6][6] 两个数字，然后发现其中有一些不需要维护，可以优化。
f[i][j] / g[i][j]匹配到i = 小于i的位置都匹配了，i没有匹配，之前已经匹配到i了，经过这个区间匹配之后，该匹配j了，这样的字符串有多少个 f，这样的字符串多出现了几次 bessie g
l 子串的左端点必须是区间的左端点
r 子串的右端点必须是区间的右端点
c 所有子串
s 子串的左端点必须是区间的左端点 && 子串的右端点必须是区间的右端点
a.l = l.l + l.s * r.l
a.r = r.r + r.s * l.r
a.c = l.c + r.c + l.r * r.l
a.s = l.s * r.s
sum(sf[i]) = 1
sf[i][0] + sf[i][1] + sf[i][2] + sf[i][3] + sf[i][4] + sf[i][5] == 1
第2题
题目解析：
所有最终的分数分成两种： > a/b 和 <= a/b
找到这个分数在 Stern–Brocot tree 中的位置，> a/b 每次得到新的分数必须更接近 a/b，<= a/b 每次得到新的分数可以和之前的相等（通分），在 Stern–Brocot tree 连续往左，或连续往右，要一起考虑。
第3题
题目解析：
支持两个基本操作：
合并两个交集为1的集合
从已有的集合中删去一个点，删去的点只属于一个集合
删一个点会带来哪些影响
会减少一些 triple
分为以下几种
自己做中间点 两边的点 来自相同一个集合 可以 P(集合大小 - 1, 2)
自己做一端点 自己和另一端点属于同一集合 可以 P(集合大小 - 1, 2) * 2
自己做一端点 自己和另一端点属于不同集合 最难 (query(S) - ask(S)) * 2
合并两个交集为1的集合 A 和 B
减去 A 的贡献
减去 B 的贡献
加上 A和B 的贡献（因为被减了两次）
加上 A合并B 的贡献
一个集合对答案的贡献：
一条链至少2个点在这个集合内，算作这个集合的
贡献：
3个都在集合内 P(集合大小, 3)
2个在内，1个在外 (query(S) - ask(S)) * (集合大小 - 1) * 2
加上 A和B 的贡献（因为被减了两次）
(A大小-1) * (B大小-1) * 2
对于每个集合 S 定义 ask(S)
ask(S) 存在点 不仅在自己这个集合，还在其他的集合
点的个数
query(S) 存在点 不仅在自己这个集合，还在其他的集合
其他集合的大小之和
每个点记录自己属于哪些集合 （只属于一个集合的可以不计）
集合S 如何维护
集合S 大小 （简单）
ask(S) 可以维护
query(S) 维护困难
把 A和B 合并之后
query(A并B) 的维护 简单
A合并B 之后 原本和A交集为1的集合C的 query(C) 怎么维护 ???
删一个点对
集合S 大小 -= 1
ask(S) 无
query(S) 无
对于原本和S交集为1的集合的影响 ???
邻居：自己集合 和 其他集合 交集的点
每个集合维护query(S)
缺点
一旦自己发生改变，需要通知所有的邻居，自己的邻居可能很多
每次需要query(S)时，立刻询问所有邻居的大小并求和
缺点
自己的邻居可能很多，一个一个问太慢
邻居比较多 = 邻居个数 > sqrt(n)
折中办法
一旦自己发生改变，只通知 邻居比较多的 邻居
至多通知 sqrt(n) 个邻居
需要询问自己时，判断自己是否邻居多
如果多，那么直接回答（靠别人通知自己）
如果少，询问所有邻居的大小并求和
【竞赛报名/项目咨询请加微信：mollywei007】
