USACO真题（黄金）真题解析带你拿下量产藤校的权威竞赛

明天就是USACO 2月赛啦，2月26日开启的3月赛也迫在眉睫了。今天给大家分享一道去年12月新鲜出炉的USACO真题（GOLD）解析，希望能为你拿下今年的比赛带来一波强助攻。

USACO真题（黄金）真题解析带你拿下量产藤校的权威竞赛内容图片_1

USACO，“对标”AIME、USAMO的计算机竞赛

USACO竞赛指的是美国计算机奥林匹克竞赛。是一项为国际学校生或者年龄更小的学员提供的在线竞赛，旨在锻炼学员用计算机编程解决问题的能力。它的全称是USA Computing Olympiad。竞赛在家里通过网上进行。与其它竞赛不同，USACO没有学校和地区级的限制

如果在此竞赛中有所斩获，一定会对本科留学申请大有裨益。随着近年来竞赛党们“背提意识”的提升，USACO已成了“必争之地”。

在国外著名网站Quora上，还有人尝试把USACO跟数学类竞赛含金量做了一个简单对比——

USACO真题解析（GOLD）

题目（2020年 12月 Gold #1）

在网上观看太多机械 DIY 视频的后果就是，Farmer John 偶然在他的农场上制造了一个可以自我复制的机器人！

农场可以用一个 N×N 的方阵表示（3≤N≤1000），其中每个方格是空的或有岩石，并且所有边界上的方格均有岩石。某些没有岩石的方格被指定为机器人可能的起始位置。

Farmer John 初始将机器人放置在可能的起始位置之一。在之后的每一个小时，机器人的所有副本会沿着相同的方向移动一格，向北、向南、向东或向西。每 D 个小时（1≤D≤109）之后，机器人的每个副本会进行自我复制——在方格 (x,y) 进行自我复制的机器人会在方格 (x+1,y)、(x−1,y)、(x,y+1) 以及 (x,y−1) 产生机器人的新的副本；原本的机器人仍然位于 (x,y)。一段时间过后，同一方格内可能会有多个机器人。

如果移动或复制会使得任何一个机器人撞到岩石，那么所有的机器人均立刻停止行动。注意这意味着所有机器人最终必然会停下，由于农场的边界都是岩石。

请帮助奶牛们求出可能在某个时刻含有机器人的空的方格数量。

USACO真题解题思路

首先考虑问题的2个简化版：

（1）机器人只能原地复制，每过D小时，尺寸(sz)增加1，直到碰到石块；

（2）机器人不会复制，如果没有石头阻挡每小时可以向E/S/W/N一格，机器人有个属性sz，每过D小时sz增加1，对于已经访问过的空格，如果当前szcur > szold，还可以再次访问。

对于问题（1），如果我们能够事先知道空格(i，j)到最近石块的距离dist[i][j]，对于以(i，j)为中心尺寸为sz的机器人，只要 sz< dist[i][j] 便可容纳。我们可以通过BFS遍历，预计算每个空格到最近石块的距离dist[i][j]（当(i，j)是石块时，dist[i][j]=0），然后对每个机器人位置直接进行判断。

对于问题（2），我们用grid记录空格，当(i，j)是空格时，grid[i][j]=true；起始点S另外记录到start。通过BFS进行遍历时，我们还需要额外记录step(每经过D小时，sz增加1，其它时刻向所有可能的方向移动一步)；因为需要比较sz，我们可以用center[i][j]，记录最近经过(i，j)时机器人的sz。

结合（1）和（2），经过2次BFS，我们可以通过center获得，机器人中心能够到达的所有(i，j)，以及最后经过(i，j)时机器人的sz（center需初始化为-1）。下一个挑战是要计算机器人占领的格数。

考虑center[i][j] = k，向外一步，(i-1，j)，(i，j-1)，(i+1，j)，(i，j+1)可记录扩散值为k-1，向外2步，(i-2，j)......(i，j+2)录扩散值为k-2，直至0。考虑被覆盖的空格(a，b)，它可以是以(i，j)为中心机器人覆盖的，或是以(p，q)为中心机器人覆盖的，我们只需记录扩散到(a，b)的最大值；(a，b)将向其周围扩散值更小的格子扩散。所以，这里需要再次用到BFS遍历，按扩散值从大到小进行遍历，由于扩散值会动态变化，需要用到优先队列deque<>，每次从队列中获取扩散值最大的下个点。最后统计所有扩散值非零的点。

今日份USACO真题解析就到这里，提前祝大家都能赛出佳绩。

对于想进牛剑G5藤校的学员来说，考试成绩都不会差，拼的就是以竞赛为代表的软实力。如果你还不知道如何冲刺复习USACO二月赛和公开赛，或者在为平衡课堂学习与竞赛复习的时间纠结不已，点击预约试听【橡沐竞赛复习班】，橡沐教学天团授课，深谙不同国际课程比赛的思维框架和能力要求，介绍联想、类比、归纳、转化、试误等答题技巧，补充生僻知识点，针对每个细节精准复习，分数及学术能力双双提升。

USACO真题（黄金）真题解析带你拿下量产藤校的权威竞赛内容图片_3