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(inti =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++;// 草皮数 +1intplantPos = 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;}boolok =false;for(inti =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 -> 1if(only1[i][0] ==0|| only1[i][0] == all[i][0]) {ok =true;mask[i] =1;}// all 1 -> 0 or all 1 -> 1if(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(有向无环图），立马可以想到写一个拓扑排序即可搞定。

核心代码如下：

voiddfs(intcur,intfa){for(intto : 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的倍数，结果先手必赢。

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

核心代码如下：

intminwin = INT_MAX, minlose = INT_MAX;boolfirsthandWin =true;for(inti =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";elsecout<<"Farmer Nhojn";

第3题

题目解析：

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

核心代码如下：

x[1] =666;// 初始值挑个你喜欢的数即可x[2] = x[1] + a[t[1]][t[2]];// t[i]映射原始位置intsign =1;// cnt记录有多少个数和前一位不同for(inti =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 edgeslong long f3[320]; // 1 to i 3 edgeslong long f4[320]; // 1 to i 4 edgeslong long g3[320]; // i to n 3 edgeslong long g4[320]; // i to n 4 edgesd1[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]);}//f3g3assecondedgefor(intj=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]);}//f3g3asthirdedgef3[y] =min(f3[y],d2[1][x] +d1[x][y]);g3[x] =min(g3[x],d1[x][y] +d2[y][n]);//f4g4assecond/thirdedgefor(intj=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]);}//asfourthedgef4[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的个数。