【福利】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++; // 草皮数 +1int 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 -> 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(有向无环图），立马可以想到写一个拓扑排序即可搞定。
核心代码如下：
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 John\n";elsecout<<"Farmer Nhoj\n";
第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 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]);}// 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 edgefor (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的个数。
想要参加USACO比赛，但是晋级率不高，总是通不过怎么办？奇点编程USACO专业教练团队为你一路领航！
先来看看往年赛季战绩如何
奇点编程
往年赛季USACO战绩
2021-2022赛季
< 美国国家集训队Offer 2枚 >
< 美国国家女子集训队Offer 1枚 >
< 铂金组全球前100强4位 >
< 22位学生晋级铂金 >
< 38位学生晋级黄金 >
晋级银级人数较多，不一一统计...
2020-2021赛季
< 美国国家女子集训队Offer 1枚 >
< 铂金组全球前100强3位 >
< 15位学生晋级铂金 >
< 26位学生晋级黄金 >
晋级银级人数较多，不一一统计...
2019-2020赛季
< 铂金组全球前100强2位 >
< 10位学生晋级铂金 >
< 19位学生晋级黄金 >
完成铜级训练的学生全部晋级银级...
2018-2019赛季
< 美国国家集训队Offer 1枚 >
< 铂金组全球前100强1位 >
< 2位学生晋级铂金 >
< 5位学生晋级黄金 >
< 12位学生晋级白银 >
>> 美国国家集训队Offer <<
靓丽成绩在USACO领域独领风骚，整个赛季期间，能够在官方题解公布前原创发布各个组别全部题解，真硬核！
此系列题解为官方题解公布前奇点编程原创发布，敬请关注文末公众号！
2021-2022赛季 US Open 试题解析
2021-2022赛季 2月赛试题解析
2021-2022赛季 1月赛试题解析
2021-2022赛季 12月赛试题解析
2020-2021赛季 US Open 试题解析
2020-2021赛季 2月赛试题解析
2020-2021赛季 1月赛试题解析
2020-2021赛季 12月赛试题解析
2019-2020赛季 US Open 试题解析
2019-2020赛季 2月赛试题解析
2019-2020赛季 1月赛试题解析
2019-2020赛季 12月赛试题解析
USACO 2020-2021赛季数据解读
USACO 2019-2020赛季数据解读
你的同学们来自哪里？ |
遍布美国、加拿大、英国及中国的国际学校和公立牛校 |
·菲利普斯埃克塞特中学 Phillips Exeter Academy ·菲利普斯学校安多佛 Phillips Academy Andover ·圣保罗中学 St. Paul's School ·劳伦斯威尔高中 The Lawrenceville School ·霍奇基斯中学 The Hotchkiss School ·乔特罗斯玛丽中学 Choate Rosemary Hall ·迪尔菲尔德学院 Deerfield Academy ·希尔中学 The Hill School ·韦伯中学(加州) The Webb Schools (CA) ·圣马克学校 St. Mark's School ·北野山高中 Northfield Mount Hermon School ·肯特高中 Kent School ·西储学院 Western Reserve Academy |
·菲斯登中学 The Fessenden School ·鹰溪中学 Eaglebrook School ·菲尔中学 Fay School ·卡迪根山中学 Cardigan Mountain School ·岚基昊学校 Rumsey Hall School ·印第安山中学 Indian Mountain School |
· 上海：包玉刚、世外、上外、星河湾、上中国际、 美国学校、平和、领科、光华剑桥、WLSA、 加州汇点高中、诺德安达 · 深圳：深中、深外、深国交、深圳贝赛斯、 惠州贝赛斯、广州贝赛斯 · 北京：人大附中、北大附中实验、清华附中、 清华国际、德威国际、顺义国际、 鼎石国际、哈罗国际 · 香港：汉基、哈罗等学校 |
对于含金量和竞争力如此高的赛事，你是否已经动了心？
奇点编程USACO教练团队为你量身筹划比赛方案，高效训练。USACO各个级别辅导课程，C++/Java编程语言均可，就等你来！
USACO各级别课程，大牛老师们亲自授课，还可一对一、团课组班，更多课程和详细安排请添加文末教务微信咨询：
为什么选择奇点编程?
学编程，当然要选专业的。奇点编程自2015年成立以来，一直专注于中小学编程竞赛，深耕编程教研和教学，擅长从零基础开始教学，拒绝一味地堆砌知识点，疯狂填鸭式的教学。
奇点旗下编程讲师及奥赛教练，接受过严格的专业及教学培训，包含多位NOI金牌选手和国家集训队成员，拥有丰富ACM/NOI/USACO比赛经历和傲人成绩，拥有微软、Oracle、IBM、BAT等国内外著名IT企业工作经验，能够给与孩子无天花板的全方位培训。
我们教给学生的，不仅仅是编程，更是将讲师们多年在IT行业的积累与对孩子教育经验融汇贯通，教给孩子的不只是枯燥的学习经验，而是更有趣、更丰富、更人性化的编程思维，是对孩子终生的影响，而不仅仅局限于考试和比赛！
☑ 奇点编程与德儿塔编程创始人，中国计算机学会认证NOI教练。曾就职于IBM、SAP两家世界500强IT企业，担任过中国首套智能银行系统研发团队Team Lead、ASE中国讲师团成员，赴德国总部接受过专业的编程讲师培训。
☑ 精通C++，Java等多门编程语言和算法，全职从事国内外信息学奥赛等编程竞赛培训，教学经验非常丰富，善于引导激发孩子们的内在学习动力，讲解深入浅出，类比生动形象，已经从零基础培养出数百名学生在NOIP、USACO、ACSL等编程竞赛中斩获傲人奖项。
☑ 清华大学计算机系
☑ NOI2012全国金牌、IOI2013国家集训队
☑ NOI2016命题人、ICPC2015EC-FINAL金奖
☑ 2017全国信息学竞赛冬令营主讲人
☑ 2017、2018江苏省队集训教练
☑ 北京大学计算机系
☑ NOI2017全国金牌、IOI2018国家集训队
☑ NOI2016全国金牌、IOI2017国家集训队
☑ NOIP2015~2018连续四年一等奖
☑ 清华大学计算机系
☑ NOI2016金牌、 IOI2017国家集训队
☑ CCSP2017全国第三名 (CCF大学生计算机系统与程序设计竞赛)
☑ 清华大学计算机系学生算法与竞赛协会前副主席
☑ 清华大学计算机系
☑ NOI2015金牌、 IOI2016国家集训队
☑ APIO2015世界金牌
☑ NOI2015冬令营金牌
☑ 清华大学软件学院
☑ NOI2017、NOI2016银牌
☑ APIO2017、APIO2016银牌
☑ NOIP2013~2017连续四年一等奖
☑ 北京大学计算机系
☑ 2016全国信息学竞赛冬令营金牌
☑ NOI2016全国银牌
☑ IOI2016国家队选拔赛银牌
☑ 985/211高校计算机硕士，优秀毕业生, SAP中国研究院高级软件工程师。
☑ 擅长C++，Java，Python等多门编程语言，精通算法设计，曾获得国际大学生程序设计竞赛（ACM/ICPC）上海赛区一等奖。擅长USACO和NOIP算法、AP计算机教学，已培养出几十名NOIP和USACO获奖学生。
☑ 985/211高校计算机硕士，高级软件工程师，就职于著名的Autodesk, SAP。
☑ 擅长C++, Java, Python等多门编程语言，精通算法设计，擅长USACO和NOIP算法、AP计算机教学，已培养出几十名NOIP和USACO获奖学生。辅导过哥伦比亚大学、杜克大学等多位学生Python数据分析课程。
☑ 985/211高校软件工程硕士，瑞典乌普萨拉大学访问交换生。SAP中国研究院高级软件工程师。
☑ 擅长Java，C++等多门编程语言，以及JavaScript，HTML，CSS等Web前端开发技术，拥有业内领先的大型软件系统开发经验，善于沟通与换位思考。擅长USACO和NOIP算法、AP计算机、ACSL教学，辅导过的AP计算机学生全部5分，同时也担任企业内部培训师，敏捷软件开发教练。
☑ 985/211高校计算机硕士，系统架构师, 十六年计算机软件研发经验，就职于花旗银行，SAP，担任企业内部技术培训师，敏捷软件开发教练。
☑ 擅长C++，Java，Python等多门编程语言，赴德国总部接受过专业的编程讲师培训，擅长USACO和NOIP算法、AP计算机教学，已培养出数十名NOIP和USACO获奖学生。能够辅导计算机相关作业，熟悉留学科创作品。
☑ 985/211高校计算机专业，技术经理，就职于著名的瑞士再保险、币安、惠普等。
☑ 擅长C++, Java , Python等多门编程语 言，曾获得国际大学生程序设计竞赛 (ACM/ICPC)浙江赛区奖项。擅长USACO 和NOIP算法教学，已培养出多名NOIP和USACO获奖学生，具备出色的问题分析解决能力。能够辅导计算机相关作业，熟悉留学科创作品。
☑ 985/211高校计算机硕士, 系统架构师，亚马逊云解决方案架构师，金融行业咨询顾问，就职于著名的IBM。
☑擅长C++, Java , Python等多门编程语言，擅长USACO和NOIP算法、AP计算机教学，授课风格温文尔雅，循循善诱，已培养出多名NOIP和USACO获奖学生，能够辅导计算机相关作业，熟悉留学科创作品。
☑ 985/211师范院校出身，高级工程师，曾就职于著名的保时捷集团，SAP，持有PMP、 SCJP、ISTQB等多项业界认证。
☑擅长C + +, Java , Python等多门编程语言，擅长USACO和NOIP算法教学，授课风格温文尔雅，循循善诱，培养出一大批基础扎实的学生，深受孩子和家长们的欢迎和信赖。
☑ 青少儿编程教学专家，985/211师范院校出身，擅长Scratch从入门到竞赛全程教学，NOIP入门组教学。
☑ 擅长Scratch，C++，Python等多门编程语言, 授课风格温文尔雅，循循善诱，深受孩子家长们的欢迎和信赖，已经从零基础培养出数十位Scratch比赛一等奖获得者。
☑ 985/211高校计算机硕士,曾就职于百度研发中心，曾获“蓝桥杯”大学生C++程序设计大赛一等奖。
☑ 熟悉C/C++, Java，Python,授课风格亲切自然，深受孩子喜欢。
微信扫码关注该文公众号作者