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

各位同学度过了上周紧张又充实的一个周末，不少考铜级的同学会觉得相比上个月，本次铜级难度往下降低了一些，没有特别难的题，心情愉快的同学很多。本次银级也是相当的良心，各位有没有抓住这一波升金的机会呢？本次金级和铂金级共6道，其中4道题都是由Benjamin Qi大佬单独命题，另外2题他也参与了命题，直接把金级难度拉爆了，异或运算、逻辑推理、线性代数、特别复杂的递归
。发现避开Benjamin Qi命题的场次居然也可以成为一种晋级策略了！
 所以不要把晋级的希望全部寄托在某一场比赛中，多参赛几回，晋级概率会大许多！
推荐各位同学认真读一读题解，把握一下比赛难度的变化趋势。
更多内容，请参考下文解析。
大家的眼睛是雪亮的，成绩不是靠口头喊出来的，而是需要一步一步长期耕耘才能结出硕果。能够在官方题解公布之前，原创全部组别题解的机构，是真硬核！
（
需要转载的请注明来源，尊重他人劳动成果
）

以下内容是各大级别的赛题解析，供同学们参考交流。想要咨询参赛和备考冲刺计划的同学，可以扫描文末二维码，添加老师微信获取。
第1题
题目解析：
分别计算出H、G的第一个和最后一个位置，然后分别计算出h为leader的个数hcnt，g为leader的个数gcnt, 答案就是hcnt*gcnt。
核心代码如下：
for(int i=1; i<=ldg; i++){if(s[i-1]=='H' && e[i]>=leaderg && !book[i]){ hcnt++; }}for(int i=1; i<=ldh; i++){if(s[i-1]=='G' && e[i]>=leaderh && !book[i]){ gcnt++; }}cout<<hcnt*gcnt<<endl;
第2题
题目解析：
这里有m个空调，每个空调要么开要么关，所以这m个空调就有2^m可能组合，可以暴力枚举所有组合，看看那些组合满足温度调节的要求，并计算满足条件的组合里面花费，并求出最小花费。
由于空调数量为变量，因为不能用多重循环直接枚举所有组合，可以利用二进制来表示组合情况，直接用位运算或者转换为二进制字符串形式来处理。
核心代码如下：
// 方法1：利用位运算for (int i = 0; i < (1 << m); i++) {memset(reduce, 0, sizeof(reduce));int status = i, money = 0;for (int j = 0; j < m; j++) {if (status & (1 << j)) {for (int k = air[j].a; k <= air[j].b; k++) { reduce[k] += air[j].p; } money += air[j].m; } }//...}// 方法2：将方法1中的status转化为二进制字符串int cnt = pow(2, m); // 替换1 << m// 自定义函数// string base10to2(int num, int len);string status = base10to2(i, m);    
第3题
题目解析：
枚举长度为3的全部子串，可以变为MOO的子串, 共有4种：MOO  MOM OOM OOO
最后答案按如下顺序选择：
MOO: len - 3 （len表示输入字符串长度）
MOM 或者 OOO: len - 2
OOM：len -1
否则为-1
核心代码如下：
if (hasmoo)cout << len - 3 << endl;elseif (hasmom || hasooo)cout << len - 2 << endl;elseif (hasoom)cout << len - 1 << endl;elsecout << -1 << endl;
第1题

题目解析
本题可用拓扑排序或者并查集完成。
首先统计需要变换的字母个数，然后处理特殊情况：
1，如出现一个字符变成多个不同字符的情况（比如aa变ab），则无解，就输出-1。
2，如出现环(ab变ba或者abc变bca这样）并且环上所有点的入度全部为1，则需要其它字母中转，需要额外加1次。如果环上所有点的入度全部为1，比如ABC->BAA，则不需要另加1。
3，如有环但没有中转字母的(52个字母全部在环上的情况)，则无解，就输出-1。
核心代码如下：
int ans = getAllLetters();bool allincycle = toposort();int cyclecnt = findcycles();if (allincycle && sum == 52 && cyclecnt > 0) {// 有环但没有中转字母的(52个字母全部在环上)，则无解，就输出-1cout << "-1" << endl;return; } ans += cyclecnt;
第2题
题目解析：
本题是一道模拟题，放在铜级考也不算过分。按照题意模拟走的过程，先统计不做任何反转时需要的成本，再去枚举每个被反转的位置，减去经过这个位置的牛原来需要的成本，再加上反转方向后需要的成本，即可得到新的成本。需要注意的是，每个位置有几头牛需要预处理好，否则会超时。
核心代码如下：
for (int i = 1; i <= n; i++) {   ans += cowcnt[n + 1][i] * cost[n + 1][i] + cowcnt[i][n + 1] * cost[i][n + 1];}cout << ans << endl; // 不做任何反转时需要的成本for(int i = 0; i < m; i++) { cin >> x >> y;if (dir[x][y] == 'D') { flip(x, y, 'R'); } else { flip(x, y, 'D'); } cout << ans << endl;}
‍
第3题
题目解析：
本题是一道贪心题，最佳策略：在左右两端时往中间走，其余位置判断该点左右两侧经过次数大小，当a[i] <=a[i+1]，往右走，否则往左走，即可保证转向次数最少。为什么原因呢？因为起点在最左侧，最终还是要回到起点，移动过程中，如果左侧经过次数大，此时往左转向的次数是不会浪费的。
核心代码如下：
for(int i = 0; i < steps; i++) {if (pos == 0) { cout << 'R';pos++; a[pos]--; } elseif (a[pos + 1] >= a[pos]) { cout << 'R';pos++; a[pos]--; } else { cout << 'L'; a[pos]--;pos--; }}
第1题
题目解析：
第2题
题目解析：
第3题
题目解析：
第1题
限于篇幅，Platinum题目就不贴了
需要者可以扫描文末二维码，添加老师微信获取
题目解析：
暴力做法
从起点开始，每次尽量往右跳，如果能直接跳到终点，就跳到终点
从终点开始，每次尽量往左跳，如果能直接跳到起点，就跳到起点
有多少个特殊的点可能在最短路上
如果一个点在最短路上是第k个，那么他只可能是第k个
可能成为最短路上的第k个点的点是一个连续的区间（只需要找到最左可能的点，最右可能的点）
最右可能的点 从起点开始，每次尽量往右跳
最左可能的点 从终点开始，每次尽量往左跳
最终答案就是
从a尽量往右跳，跳到b之前每个点左边(包含自己)的特殊点个数
减掉
从b尽量往左跳，跳到a之前每个点左边(不含自己)的特殊点个数
的差
特殊处理起点终点
倍增优化
f[i][j] 从i出发，往右跳2**j步，记录2个值，跳到了哪里，跳到的所有点 左边(包含自己)的特殊点个数
g[i][j] 从i出发，往左跳2**j步，记录2个值，跳到了哪里，跳到的所有点 左边(不含自己)的特殊点个数
对于每组询问
起点尽量往后跳，但不能超过终点（等于也不行）
起点尽量往前跳，但不能超过起点（等于也不行）
第2题
题目解析：
s[i]表示i集合中所有点mana恢复速度之和
a是任意两点之间距离，读入之后做Floyd
f[j][i]表示走i集合以点j结尾亏多少mana（如果全在最后收割，可以收获集合s[i]的所有mana*时间t
但因为有走路时间，会亏f[j][i]
初始化 f[i][1 << i] = 0 从i开始，然后立刻结束
转移
当前已经走过i集合，以j结尾，再走一步从j到k，需要花费a[j][k]的时间
在这段时间s[i]集合中的mana没有采集到，亏了a[j][k] * s[i]
f[k][i | 1 << k] = min(f[k][i | 1 << k], f[j][i] + a[j][k] * s[i]);
希望亏得越少越好
把所有询问离线处理，按点分组p[]，同一组中的所有询问按时间从小到大排序
对于同一个终点i的所有集合j，可以生成一堆pair（类似一次函数的斜率和截距）
截距 亏了多少，斜率=j集合中所有mana恢复速度之和s[j]
如果花费t的时间，选择第k个pair，那么收益是 c[k].first + c[k].second * t
但是c数组很大，不能一个一个枚举求最大值，所以采用凸包的思路
按截距从大到小排序
对这些pair需要用单调栈求凸包
对于同一个终点的所有询问，按时间排序，从小到大（双指针）依次回答
第3题
题目解析：
f[x] 表示把所有点从关到开到关，让x子树中所有点都满足条件，最小操作次数
g[x] 表示把所有点从关到开(从开到关)，让x子树中所有点都满足条件，最小操作次数
s[x] 子树大小
f[root] = 所有子树的 f 之和  + 2 * s[root] + (g[x] - f[x] - s[x])  + (g[y] - f[y] - s[y])  （任选root的2个孩子x y）
还有一种转移 f[root] = 所有子树 f 之和 + 2 * s[root] - 2 * 最大的子树
g[root] = 所有子树的 f 之和  + s[root]  + (g[x] - f[x] - s[x]) （任选root的1个孩子x）
想要参加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领域独领风骚，整个赛季期间，能够在官方题解公布前原创发布各个组别全部题解，真硬核！
【USACO考生福利礼包】
此系列题解为官方题解公布前奇点编程原创发布，敬请关注文末公众号！
USACO 2021-2022赛季试题解析系列
2021-2022赛季 US Open 试题解析
2021-2022赛季 2月赛试题解析
2021-2022赛季 1月赛试题解析
2021-2022赛季 12月赛试题解析
USACO 2020-2021赛季试题解析系列
2020-2021赛季 US Open 试题解析
2020-2021赛季 2月赛试题解析
2020-2021赛季 1月赛试题解析
2020-2021赛季 12月赛试题解析
USACO 2019-2020赛季试题解析系列
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各级别课程，大牛老师们亲自授课，还可一对一、团课组班，更多课程和详细安排请添加文末教务微信咨询：
01
USACO 零基础语言班
02
USACO 青铜级训练营
03
USACO 白银级训练营
04
USACO 黄金级训练营
05
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,授课风格亲切自然，深受孩子喜欢。
继续阅读
阅读原文