USACO美国信息学奥赛
2024-25赛季3月公开赛已落幕
同学们都“打怪升级”成功了嘛？
为帮助同学们高效复盘，翰林卫老师照例为大家带来3月公开赛的考情分析，快来和小林一起了解详情吧！
USACO 3月公开赛分析——铜级篇
01、近年分数线
25年3月的分数线是700，这个赛季铜级全部是700分。只需要2题全对，第3题通过10%的测试数据就可以。
02、竞赛难度分析
这次铜级的难度，从官方给定的700分数线推断，应该定位在一个平均偏上的位置（750是一个平均难度）。值得关注的是，这次open赛的难度并没有比前三场大，晋级可能比前面的场次还容易点（考虑到多了1个小时的比赛时间）。
03、考点分析
第一题【Ad Hoc】
这道题需要应用到一些【排列组合】的知识，计算会输的方案数会更容易。每次只需要计算出同时能赢s1和s2的个数，那么只要方案里面没有这些，就肯定会输。相比于这个赛季出现过的【Ad Hoc】，难度并没有加大，还是比较容易想到的。
第二题【Greedy】
需要大家去观察，找到贪心思路的一道题。多尝试点例子，就可以发现，从大到小第一个出现频率大于等于1的数，就可以作为中间那个元素。后面只要出现个数大于等于2的，都可以算2个进去。和这个赛季之前的【Greedy】相比，思维难度更小，而且代码实现也很容易。
第三题
【Complete Search + Prefix Sum + Binary Search】
三道题中最难的一题。如果前两题全对，这道题直接最暴力的做法，答对前2个test case，就可以晋级了。
想要拿满分，需要用【Prefix Sum】快速找到第一个不是该字母的位置，用【Binary Search】找到最后一个该字母的位置。中间的位置，需要结合数学知识，推理出来就是最接近两者中间的位置。
总体而言，铜级的考点分布比较均衡，也都是我们平时强调的重点。而且此次open赛的难度相比于去年明显降低，和常规赛差别不大。同时给的时间多了1个小时，所以相对更容易晋级。不过想要拿满分，需要有一些银级的知识储备，同时善于结合数学分析。
USACO3月公开赛分析——银级篇
01、近年分数线
25年3月的分数线是750，这个赛季前面都是700，这场达到750分，和去年的常规赛一致。所以大家为了确保自己晋级，最好还是要达到750分以上。
02、竞赛难度分析
这次银级的难度，从官方给定的750分数线推断，也是定位在一个平均的位置。这次的银级，同样也是需要大家具备一定的分析能力，没有太过套路的题目。和前面的场次一样，逻辑和算法的考察都有，想要晋级两方面能力缺一不可。
03、考点分析
第一题【Greedy】
是一个带贪心的构造题，突破口在于发现popcount比总和更难凑出来，所以构造出满足popcount总和是k，数值总和最小的解。这样的好处，就是后面可以在不影响popcount的基础下，去凑总和。
具体又要分情况讨论，比如总和已经大于m、总和差是偶数、相差大于3、相差1等，每一种都需要自己去结合具体实例分析，对大家的逻辑要求比较高。这道题关键在于选对方面，如果大方向错了，基本上不太可能对。
第二题【Graph + Greedy】
最终可以转换成一个Graph的模型，和23年1月份的【Find and Replace】有点类似。可能形成多个component，每个是一个纯链、带环（只有一个元素）的链、环（只有一个元素）。
后面就是贪心的思路，优先从链那头出发让相邻去匹配，最后环中剩余的自己相互匹配。是一道需要建模的题，同时自己也要去思考会出现的情况，找到正确答案。
第三题【Tree + Binary Search】
构造出一个以1为root的tree。最核心的部分是计算，每个node在每个勇气值下，能回到1的最小技巧值。这个可以通过dfs中维护一些信息完成，也就是从1到该node的路径中最大的11个数值。得到这个信息以后，再按照勇气值归类，后面查询用二分就可以。
这道题的代码细节有点多，也要注意超空间的问题，相比于前两道题，这道题的逻辑要求没有那么高，比较常规。
总体而言，银级的有偏思维也有偏算法的题，特别是前两道都需要Greedy，会比较难想。想要达到750分，基本上每道题都得有一个比较正确的方向，难度会比之前的场次大一点。
USACO 3月公开赛分析——金级篇
01近年分数线
25年3月的分数线是850，相比于整个赛季之前的700分，有了非常大的提升，甚至也是近4个赛季中的最高分。这就提醒大家，有时候800分也不太保险，850才是一个比较稳妥的分数。
02、竞赛难度分析
这次金级的难度，从官方给定的850分数线推断，也是定位在一个平均往下的位置。比之前的场次分数线大幅提升，但其实这场的难度也不算低。可能大部分同学完成得都不错，导致了分数线的提升。
03、考点分析
第一题【Math】
一道很偏数学的题目。可以考虑单个字符串内部的方案数，如果是m的话，答案就是m^L。单个字符串内，又可以通过从后往前遍历的方式，遇到O进行累加，遇到M从还剩余的O中选择K个，看有多少种方案，这是一个组合问题。
代码实现层面，要用到【Modular Arithmetic】、【Combinatorics】等内容。可以先作为一道数学题去思考，对大家的数学逻辑思维要求比较高。
第二题【Square Root Decomposition】
这个赛季第二次考到了铂金的这个考点。关键需要发现，两个牛要作为leader，必须它们的票数总和大于等于最高票数。直接暴力枚举会O(N^2)，可以从票数种类出发枚举，这样就可以缩减至sqrt(N)级别。大家可以考虑学一些铂金的重点算法，在金级的比赛中，也是会有帮助的。
第三题【Ad Hoc + Binary Search + Segment Tree】
首先也是策略的考察，前者会把最大的A个加1，后者会把最大的B个减1，其实受影响的只有中间A-B个。直接模拟会超时，可以先全部考虑加1操作，用Binary Search去二分找到所有大于等于mid的减到mid或者减去D 次，是否可行。
还有一种方式是使用【Segment Tree】，考虑怎么去合并区间，这个对代码的要求更高。
总体而言，金级的考点不算是很常规，逻辑题有点多。除了第一题比较常规以外，剩下的两道题都是有思维难度的。分数线是850分，对大家的要求很高，特别是又出现了铂金的考点。
24到25赛季，已经全部结束。除了open赛，每个级别的分数线，都是700分（open赛金级分数比较反常）。这次open赛没有之前那么难，特别是铜级，甚至比之前还简单。所以大家下个赛季也可以多多关注open，也是一次比较好的机会。
距离下个赛季还有8个月的时间，大家可以利用这段时间，多多学习算法知识，练习题目做积累。USACO是一个需要花费时间的比赛，循序渐进，充实提高自己的能力，我们下个赛季见。
🔼 以上内容由翰林计算机卫老师提供
翰林计算机卫老师
清华大学软件工程硕士
南京大学软件工程学士
◾ 毕业后在一家上市视频监控公司，从事软件开发工作，负责核心流媒体中台项目，担当公司最新技术的探索和转化职责。
◾ 教学方面，对待学生耐心负责，讲解知识深入浅出，在有限知识内最大化地实现教学目标。
◾执教战绩（部分）：
-2024-2025 NZOI赛季，辅导1名学生入选新西兰国家队，参加国际信息学奥赛IOI；
-2024-2025 USACO赛季，辅导2名学生晋级铂金，15名学生晋级金，16名学生晋级银；
-2023-2024 USACO赛季，辅导3名学生晋级铂金，9名学生晋级金，14名学生晋级银；
-2022-2023 USACO赛季，辅导5名学生晋级金，11名学生晋级银。
了解USACO信息学奥赛详情
可扫码添加顾问咨询
我要领取！
USACO 2024-25赛季圆满收官在翰林导师与学员的携手拼搏下
我们交出了一份亮眼的成绩单！
12月月赛：1铂金 7金 17银
1月月赛：9金 9银
2月月赛：3铂金 7金 10银
3月公开赛：1铂金 2金 2银
共5位铂金级别、25位金级和38位银级选手！
USACO 2023-2024赛季完美收官！
2024-25赛季USACO战绩
USACO 12月月赛
晋级铂金：1人来自北京第十一中学
晋级金级：7人来自深国交，美高，German Swiss International School，杭州外国语学校等
晋级银级：17人来自上海星河湾，包玉刚，香港哈罗，杭州惠立，Mecleans College，WLSA上海，成外，加高，英国私立高中等学校
USACO 1月月赛
晋级金级：9人来自美亚学校，成外，星河湾，杭州外国语学校，包玉刚杭州惠立，Mecleans College等
晋级银级：9人来自清澜山，美高，成都美视学校，成都高中，星河湾，贝赛思等
USACO 2月月赛
晋级铂金：3人来自美高、深国交等
晋级金级：7人来自人大附、WLSA、美高等
晋级银级：10人来自上海星河湾、北京21世纪、贝赛思、美高等学校
USACO 3月公开赛
晋级铂金：1人来自英国私立高中
晋级金级：2人来自上海星河湾，马尼拉国际学校
晋级银级：2人来自多哈高中，IGB
正如翰林卫老师所说的，计划参加USACO信息学奥赛新赛季的同学可以趁这段时间系统学习算法知识，通过刷题夯实基础。
为了帮助大家高效备考，翰林推出了USACO各级别班课。由哥大和清华学姐带队！为参赛者提供专业的指导和实战经验分享。
了解USACO课程更多内容
可扫码1v1咨询顾问老师哦~
我要咨询！
本期福利
2024-25赛季USACO
3月公开赛真题
添加顾问老师免费领取
