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

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

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

第1题

题目解析：

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

第2题

题目解析：

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

第3题

题目解析：

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

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

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