2022年2月USACO竞赛银级的赛题难度解析!

美国计算机奥林匹克竞赛USACO 已经是全美计算机含金量和竞争力最高的赛事之一。本赛季最后一次月赛USACO OPEN将在3月25日至28日举行。2月赛已结束,今天对2022年2月USACO竞赛银级的赛题难度解析!为学员们参加3月的OPEN组(3月25日-3月28日) 提供参考。USACO的关注度和参与度每年都在增加,难度也在逐渐提升!

距离3月月赛开始还有3周的时间,大家可以好好回顾总结一下之前两场的题目,争取在3月的比赛中取得突破性的结果!以下内容是白银级别的赛题解析,供同学们参考交流。

第1题

备战公开组 |USACO 2022年2月白银回顾

题目解析:

白银级第一题可以直观的看出,对于第i行里面的数,i后面的都不用考虑在内,因为一开始拿到的就是i,不可能交换降级。所以我们可以从图论的角度出发,左右分别建立节点,例如中的1-4,每次左边的点可以根据喜好连接到右边,最终我们需要尽可能匹配最多的边(需要注意的是,每次选边的时候,不能重复覆盖点)。到这一步,题目转化为二分图的匹配问题,直接DFS求解。

第2题
备战公开组 |USACO 2022年2月白银回顾
题目解析:

第二题初步看似一个BFS搜索题目,每一个指令节点看做一个状态,然后通过指令间的转移,一步步到达重点。最多搜索层数为N层。但是这种方法会超越题目要求的内存限制。本题应该通过二进制来表示所有指令的组合方式,通过一个数字表示一个状态,然后将所有状态序列计算出来并且按坐标排序,最后通过二分搜索来寻找查找需要的位置。需要注意的是,本题的二分搜索数组序列不再是单个数,而且坐标表示的序列,需要认为来定义优先级。

第3题

备战公开组 |USACO 2022年2月白银回顾

题目解析:

第三题是模拟类题目,可以分析得出左边的文件夹只能往下翻不能往上分。右边的邮件可以往上翻,前提是将邮件挪动到左边。可以一开始统计出需要搬运的邮件标号,例如1,2,3,4,5。每次遇到一个就搬到左边。并且清空这个记录。但是右边遇到一个,需要搬运左边的时候,要将左边将下翻的前提是本邮件号前面的都已经放置在左边了,不满足这个前提的话不能翻动左边,只能接着翻动右边。按照这种策略,最后判断能否把所有邮件搬运到左边,可以的话就是yes,否则就是no

想要获取备赛计划,考前查缺补漏、重点冲刺

快来扫下方二维码咨询,了解更多赛事信息及参赛经验分享~

翰林国际教育资讯二维码