
美国计算机奥林匹克竞赛(USACO) 2020 赛季在新冠疫情的笼罩下结束了, 值得关注的是,这次全球参赛人数创历史新高,中国考生人数大幅增加,境外考生总人数已经超过美国考生,和往年一样,青铜级别参赛人数增加最多。
2020赛季参赛人数总计

此赛季总体来看,题型难度有逐月递增的趋势,以青铜级别为例,十二月,一月和二月的考试难度适中,比赛的通过率在20%到30%之间,是历年来的平均水平。最后的三月的公开晋级赛难度陡增,这造成了三月的晋级人数大幅度降低,三月青铜级别的通过率只有7%。在此处添加文本段落
青铜级别晋级人数总计

这次,白银级别比赛人数也增加,十二月考试较简单,通过率在19.8%。一月至三月的考试大幅增加难度,最难的题出现在一月赛,通过率直接下降到了4.6%,之前黄金级别才出现的复杂算法题这次出现在了白银级别,不少创客营的考生都遇到了运行时间超时的现象。最后的三月公开赛中的白银级反而不是最难的,不少考生顺利晋级,通过率在12.7%。
白银级别晋级人数总计

每年黄金级比赛人数一般都相对稳定,通过率在10%-20%之间。十二月到一月考试内容偏容易,二月和三月的略难。由于黄金级和白金级题目难度高,美国国内参赛学生人数不多,所以在美本申请中的优势很明显。如果将来专业方向是理工科,或者是计算机的,一定要拿下黄金,冲刺下白金级别。
黄金/白金级别晋级人数总计

从以上分析中可以看出,这次除了白银级别在1月出现了难题之外,青铜,黄金和白金级别的难度都有逐月上升的趋势,所以2021赛季同学们一定要提前规划,在头两场的月赛中就做好充分的准备,拿到相应的级别,后2场作为补救。

下面我们为大家带来三月青铜级别比赛的考情分析
第一题

最直接思路是根据两头⽜之间的距离排序,找出最⼤两个,和最⼩比较(注意两头端点处的特殊情况)。进⼀步提⾼,我们只需要3个值:最⼩值,最⼤值,第⼆大的值,这个可以通过⼀次遍历获得。
第二题

读进来之后,按照x坐标排序,然后遍历所有未得病的s为0的奶⽜,分别计算他和身边得病的s为1的奶⽜之间的距离,这个距离的最⼩值就是R。然后从第⼀头得病的⽜开始,向前看是否有牛在R范围内,如果有,就再向前看,直到下⼀头⽜不在范围内,则计数器加1。循环往复直到最后。
第三题

穷举传染源头⽜。传染源头必然是最后被感染的⽜中的⼀个,k最⼩为0,看从这头⽜第⼀次出现的时刻向后,是否满⾜最后的结果。0不行的话就加1看看,再不行再加1,就能得到k的最⼩值。k的最⼩值的可能值最⼤是之后出现的⽜pairs数值。k的最⼤值默认是⽆穷,除⾮出现⼀头有病的⽜在x次传染后遇到另⼀头牛,⽽这头⽜最后没得病,那么k的最⼤值减⼩为x。

最后,祝贺少年创客营今年很多学生在各个级别都顺利晋级。少年创客营推出USACO 青铜/白银备赛营,还有三种编程语言 Java, Python, C++的零基础课程。备赛课程会分析讲解USACO 2020 赛季的新趋势和新题型,以及往年真题中的难题分析,尤其着重讨论运行超时的解决办法。
