USACO 2022-2023赛季试题解析系列（12月晋级赛）

大家好，USACO试题解析系列在新赛季又和大家见面啦！截至北京时间本周二晚，USACO 本赛季第一场晋级赛正式结束,  满分同学会当场晋级，没有当场晋级的同学可以耐心等待一周之内出成绩。

各位同学度过了上周紧张又充实的一个周末，不少考铜级的同学会觉得相比以往，本次铜级可谓难出天际了，上个赛季各个级别难度已经往上拉了一波，这个赛季其他几个级别难度倒还好，没有再往上拉多少，但是作为入门级的铜级还是继续在往上拉难度。

我们题解系列对于Benjamin Qi大佬多次介绍过，这次他给大家上了一课，哪怕是暴力枚举也可以烦死你。Benjamin Qi大佬给选手们带来的这道看似简单，但杀伤力极强的铜级第3题，首先一部分选手压根儿没整明白逆向工程的整个过程，淘汰！

明白之后，面对颇有挑战的枚举过程，写到崩溃，淘汰！去年笔者分析命题趋势后，告诉各位后面日子不好过哦，已然成真。

推荐各位同学认真读一读题解，感受下命题难度的提升趋势。

更多内容，请参考下文解析。

大家的眼睛是雪亮的，成绩不是靠口头喊出来的，而是需要一步一步长期耕耘才能结出硕果。能够在官方题解公布之前，原创全部组别题解的机构，是真硬核！

（需要转载的请注明来源，尊重他人劳动成果）

以下内容是各大级别的赛题解析，供同学们参考交流。

第1题

题目解析：

第一题的命题质量比较好，具有一定区分度。如果上来就打暴力解，不好意思，顶多2/3的分数给到你，注意题目中N的范围是1~10^5, 不超过O(nlogn)的时间复杂度才能通过。目前铜级中极少遇到二分，因此这个O(nlogn)通常是给咱们用sort函数做排序用的，排序处理完，再用O(n)的算法即可通过。虽然是第一题，但是没有送分，还是具备一定的区分作用，筛掉部分只会简单模拟的选手。

核心代码如下：

sort(c, c + n); // 先排序处理 long long ans = 0, minT = 0;for (int i = 0; i < n; i++) { // 注意两个int相乘结果数据范围可能会溢出 if (1LL * c[i] * (n - i) > ans) { ans = 1LL * c[i] * (n - i); minT = c[i]; }}cout << ans << ' ' << minT << endl;

第2题

题目解析：

这题也有些挑战，首先得仔细看明白题意，如何用最少的草皮满足所有牛的需求。注意题目中N的范围是1~10^5, 无脑直接暴力，顶多拿到2/3的分数。正解需要利用一个贪心策略，依次为每头牛去种草，种的位置和上一个放相同种类草的位置间隔尽可能的拉大，取决于k的值。

核心代码如下：

// 以种G为例if(curPos - lastPos > k){ cnt++; // 草皮数 +1 int plantPos = curPos; if(curPos + k < n){ plantPos = curPos + k; // 间隔尽可能大 } // 考虑目标位置被占用的情况 if(ans[plantPos]!='.' && plantPos - 1 >= 0){ plantPos--; } lastPos = plantPos; ans[plantPos] = 'G'; // 记录结果}

第3题

题目解析：

这一题给大家上了一课，哪怕是暴力枚举也可以烦死你。Benjamin Qi大佬给选手们带来的这道看似简单，但杀伤力极强的铜级题。首先一部分选手压根儿没整明白逆向工程的整个过程，淘汰！明白之后，面对颇有挑战的枚举过程，写到崩溃，淘汰！整体思路就是枚举它可能的第一个分支代码是啥，然后筛选出剩余的行，继续枚举第二个分支，依次下去，每一轮筛选出的剩余行数必须越来越少，直至全部筛选完，否则就输出"LIE"。

核心代码如下：

// mask[i] = -1待选该位置0或1皆可//         = 0待选该位置只能为0//         = 1待选该位置只能为1memset(mask, -1, sizeof(mask));filteLines(...);while (true) { // n0代表回答为0的数量、n1代表回答为1的数量 if (n0 == 0 || n1 == 0) { cout << "OK" << endl; break; } bool ok = false; for (int i = 0; i < n; i++) { // column // all[i][?]统计第i列中0和1的个数 if (all[i][0] > 0 && all[i][1] > 0) { // only1[i][?]统计所有回答为1的行中，第i列中0和1的个数 // all 0 -> 0   or  all 0 -> 1 if (only1[i][0] == 0 || only1[i][0] == all[i][0]) { ok = true; mask[i] = 1; } // all 1 -> 0   or  all 1 -> 1 if (only1[i][1] == 0 || only1[i][1] == all[i][1]) { ok = true; mask[i] = 0; } } } if (!ok) { cout << "LIE" << endl; break; } filteLines(...);}

第1题

题目解析

根据题意，要求把一棵树中的每个点的值分配均匀，首先可以利用DFS在O(n)范围内找到哪些点对之间需要搬运以及搬运的数量，如果直接输出这些有向边，答案错误。这里有个细节，过程中可能会出现搬运的起点是个负数，因此咱们需要想办法按照某种顺序输出这些边。这些有向边构成一个DAG(有向无环图），立马可以想到写一个拓扑排序即可搞定。

核心代码如下：

void dfs(int cur, int fa) { for (int to : g[cur]) { if (to != fa) dfs(to, cur); } if (num[cur] != avg) { ans++; if (num[cur] > avg) { // 子节点超平均值，子搬到父 v[cur].push_back({fa, num[cur] - avg}); num[fa] += num[cur] - avg; indegree[fa]++; } else { // 父节点超平均值，父搬到子  v[fa].push_back({cur, -num[cur] + avg}); num[fa] += num[cur] - avg; indegree[cur]++; } }}

第2题

题目解析：

此题为一个博弈论问题，我们需要找到一个必赢或必输的局面。每个房间的牛头数如果是4的倍数那么后手赢，否则先手赢。为什么呢？由于只能取1个或者不超过当前房间牛头数的质数，因此：

• 对于总数为4的倍数的情况，假如先手取1个，后手取3个，如先手取2个，后手取2个，如先手取3个，后手取1个。其余依次类推，始终保持后手取完后，剩余的数为4的倍数，结果后手必赢。
• 对于总数非4的倍数的情况，先手第一次取(N%4)个，剩下来的就是4的倍数，结果先手必赢。

经过上述分析，可知只要找到经过步数最少的一个房间看谁赢就好了，其中有个细节，就是如果有多个经过步数最小的房间怎么办呢？需要记录其中哪个房间先到达。

核心代码如下：

int minwin = INT_MAX, minlose = INT_MAX;bool firsthandWin = true;for (int i = 1; i <= n; i++) { if (num[i] % 4 == 0) { // 4的倍数那么后手赢 minlose = min(minlose, num[i] / 4); if (num[i] / 4 < minwin) firsthandWin = false; } else { // 否则先手赢 minwin = min(minwin, steps[num[i]]); if (steps[num[i]] < minlose) firsthandWin = true; }}if (firsthandWin) cout<<"Farmer Johnn";else cout<<"Farmer Nhojn";

第3题

题目解析：

此题是一道不算难的构造题，先把每个区间长度为2，差值不为0的子数组找到, 其中两个数必不相同，然后看每个区间长度为3的子数组，如果大区间差值是两个小区间差值之和，那么说明单调性相同，否则说明单调性相反，依次构造即可。

核心代码如下：

 x[1] = 666; // 初始值挑个你喜欢的数即可 x[2] =  x[1] + a[t[1]][t[2]]; // t[i]映射原始位置 int sign = 1; // cnt记录有多少个数和前一位不同 for (int i = 2; i <= cnt; i++) { if (a[t[i - 2]][t[i]] == a[t[i - 2]][t[i - 1]] + a[t[i - 1]][t[i]]) { // 差大区间差值是两个小区间差值之和，单调性相同 x[i] = x[i - 1] + sign * a[t[i - 1]][t[i]]; }else { // 否则说明单调性相反 sign *= -1; x[i] = x[i - 1] + sign * a[t[i - 1]][t[i]]; } } // 最后输出数列时要记得映射一下下标

第1题

题目解析：

观察一个贪心性质，就是说要用cones代替的那些肯定是需求最少的，按这点排序之后就肯定是先用cones再用moonies了，分成两部分背包即可。

第2题

题目解析：

用set维护所有能看到的对，修改时暴力往后找会被阻挡的对删除即可，

每对只会被删除一次，可以保证均摊复杂度通过。

第3题

题目解析：

要使得组中度数最小的点尽可能大，则用一个优先队列每次删除度最小的点即可，但这样不好统计，因此可以将这个过程倒过来变成加边，然后用启发式合并维护过程中的答案，找最大的即可。

第1题

限于篇幅，Platinum题目就不贴了

题目解析：

维护 d1 d2  f3 f4 g3 g4  6个数组，表示经过指定边数的最短路，具体见代码

long long d1[320][320]; // i to j  1 edgelong long d2[320][320]; // i to j  2 edges long long f3[320]; // 1 to i  3 edgeslong long f4[320]; // 1 to i  4 edges long long g3[320]; // i to n  3 edgeslong long g4[320]; // i to n  4 edges d1[x][y] = a[x][y];for (int j = 1; j <= n; j++) { d2[x][j] = min(d2[x][j], d1[x][y] + d1[y][j]); d2[j][y] = min(d2[j][y], d1[j][x] + d1[x][y]);} // f3 g3 as second edgefor (int j = 1; j <= n; j++){ f3[j] = min(f3[j], d1[1][x] + d1[x][y] + d1[y][j]); g3[j] = min(g3[j], d1[j][x] + d1[x][y] + d1[y][n]);}// f3 g3 as third edgef3[y] = min(f3[y], d2[1][x] + d1[x][y]);g3[x] = min(g3[x], d1[x][y] + d2[y][n]); // f4 g4 as second/third edge for (int j = 1; j <= n; j++){ f4[j] = min(f4[j], d1[1][x] + d1[x][y] + d2[y][j]); f4[j] = min(f4[j], d2[1][x] + d1[x][y] + d1[y][j]);  g4[j] = min(g4[j], d2[j][x] + d1[x][y] + d1[y][n]); g4[j] = min(g4[j], d1[j][x] + d1[x][y] + d2[y][n]);} // as fourth edgef4[y] = min(f4[y], f3[x] + d1[x][y]);g4[x] = min(g4[x], d1[x][y] + g3[y]);

第2题

题目解析：

用并查集做启发式合并 初始每条边对应并查集的一个点，对于并查集的每个点，维护一个集合，表示包含哪些点，合并集合的时候考虑2件事，有一些边加重了，算了2次，需要从答案中减去新增了多少条边。

第3题

题目解析：

总体思路是这样的，不断让字符串由短变长，支持这样几种操作

两端+H

两端+G

一端+G

考虑所有H之间的配对情况，这样就不会有错位的问题了。

不好做的是一段+G怎么做，这种情况主要是对称轴移动了1

求和是 abs(对称轴 * 2 - p[i] - p[p.size() - 1 - i])

对称轴*2增加1，abs可能增加1可能减少1

用2个变量记录（对称轴 * 2 - p[i] - p[p.size() - 1 - i] ）为正的i的个数，为负的i的个数。

在增长的过程中用一个数组记录（p[i] + p[p.size() - 1 - i]）出现的次数

为了维护差值为正的i的个数和为负的i的个数。