2020USACO真题解析 快救救奶牛叭

今天给大家分享一道与社交距离相关的2020USACO真题解析， 我们的老朋友Farmer John的奶牛正在饱受COWVID-19折磨，快点看看什么样的解题思路才能救它们吧。

什么是USACO竞赛？

USACO竞赛指的是美国计算机奥林匹克竞赛。是一项为国际学校生或者年龄更小的学员提供的在线竞赛。参加这项比赛将有效增加大学申请的竞争力。

由于编程的门槛相比数理化学习更高，USACO的含金量实际高于同类型的美国数学奥赛、美国化学奥赛等竞赛。因为大量的中国学员热衷于参加热门的美国数学奥赛、美国化学奥赛，所以USACO在中国的普及度并不高。这意味着参赛选手少，获奖选手也少，含金量自然更高。

2020USACO真题解析

题目：

一种新型疾病，COWVID-19，开始在全世界的奶牛之间传播。农夫John 正在采取尽可能多的预防措施来防止他的牛群被感染。

农夫John 的牛棚是一个狭长的建筑物，有一排共 N 个牛栏（2≤N≤105）。有些牛栏里目前有奶牛，有些目前空着。得知“社交距离”的重要性，Farmer John 希望使得 D 尽可能大，其中 D 为最近的两个有奶牛的牛栏的距离。例如，如果牛栏 3 和 8 是最近的有奶牛的牛栏，那么 D=5。

最近两头奶牛新来到 Farmer John 的牛群，他需要决定将它们分配到哪两个之前空着的牛栏。请求出他如何放置这两头新来的奶牛，使得 D 仍然尽可能大。Farmer John 不能移动任何已有的奶牛；他只想要给新来的奶牛分配牛栏。

解析：

输入(socdis1.in)：

输入的行包含 N。下一行包含一个长为 N 的字符串，由 0 和 1 组成，描述牛棚里的牛栏。0 表示空着的牛栏，1 表示有奶牛的牛栏。字符串中包含至少两个 0，所以有至少有足够的空间安置两头新来的奶牛。

输出(socdis1.out)：

输出 Farmer John 以最优方案在加入两头新来的奶牛后可以达到的最大 D 值（最近的有奶牛的牛栏之间的距离）。

如果我们希望加入新的2头奶牛之后，D尽量大，可以考虑找到2个最大的间隔，在他们中间分别插入2头奶牛。如样例的数据，2头奶牛应插入最大的2个间隔中间：

10001001000010--> 10x0100100x010

用这个方法实现代码，尽管样例是可以通过，但遇到只有一个间隔的数据就会报错。如：

000000000 --> x0000000x

100000001 --> 100x00x01

100000000 --> 1000x000x

000000001 --> x000x0001

这样，我们可以先处理只有一种间隔的情况。

伪代码：

answer = 0
if len(gaps) == 1:
    if barn[0] == barn[-1] == '0':      
        # 000000000 --> 100000001
    elif barn[0] == barn[-1] == '1':    
        # 100000001 --> 100100101
    else:                               
        # 000000001 --> 100010001   # 100000000 --> 100010001

对于有2个及以上的间隔，你可能马上会联想到，如果左边/右边是0开始的，需要特殊处理。

Case #1: 2头奶牛插入最左边和最右边的牛棚

000101000 --> x0010100x     D=2

Case #2: 1头奶牛插入最左边的牛棚，另一头插入最大间隔中间

000010001 --> x00010001 --> x00010x01      D=2

Case #3: 1头奶牛插入最右边的牛棚，另一头插入最大间隔中间

100010000 --> 10001000x --> 10x01000x      D=2

Case #4: 1头奶牛插入最左边的牛棚，并且去掉最右边的空牛棚，另一头插入最大间隔中间

0000100010 --> x00010001 --> x00010x01     D=2

Case #5: 1头奶牛插入最右边的牛棚，并且去掉最左边的空牛棚，另一头插入最大间隔中间

0100010000 --> 10001000x --> x00010x01     D=2

Case #6: 去掉最左边/右边的空牛棚，2头奶牛插入最大2间隔中间

01000100010 --> 100010001 --> 10x010x01     D=2

一开始，待进入牛棚的奶牛数是2（cnt=2）。处理左端点的时候，如果奶牛可以放到最左边的牛棚，则：

cnt = cnt - 1，

且gaps[0] = gap[0] - 1。

处理右端点的时候，如果奶牛可以放到最右边的牛棚，则：

cnt = cnt - 1，

且gaps[-1] = gap[-1] - 1。

之后根据待进入牛棚的奶牛数进行处理即可，只有cnt==0，cnt==1，cnt==2 三种情况。

伪代码： 

for i in range(N):

    cnt = 2    # 进入牛棚的奶牛数

   sorted_gaps = # 从大到小排列 gaps

    dist_2nd = sorted_gaps[1]

    if barn[0] == '0':

    if gaps[0] >= (dist_2nd + 1) // 2:

            ......

        else:

            ......

    if barn[-1] == '0':

   if gaps[-1] >= (dist_2nd + 1) // 2:

            ......

        else:

            ......

sorted_gaps=sorted(gaps,reverse=True)

  answer = sorted_gaps[-1] + 1       

    if cnt == 1:                       

        answer = ......

    elif cnt == 2:                     

        answer = ......

有关2020USACO真题的解析就到这里，如果你有更好的idea，欢迎和我们交流。

竞赛是进入知名大学的关键助力之一。纵观橡沐今年113位牛剑录取的学员，大部分学员手里都握着各种竞赛奖项：AMC，UKCHO，BBO、USACO......但竞赛毕竟只申请的环节之一，如果因为准备竞赛忽略了GPA进阶就得不偿失了。而且参加USACO的选手普遍年龄较小，更需要专业的导师让他们慢慢熟悉竞赛节奏，想让竞赛、GPA双赢，点击预约试听【橡沐竞赛复习班】——

知名大学海归一线竞赛导师授课

精准匹配同一学力考生

对知识模块进行全面系统教学

扫清学习过程中的各种障碍

帮助学员构建思维模型

全面启发竞赛思维

激发国际课程热情

更多竞赛复习攻略点击

USACO竞赛是什么 提升知名大学竞争力就靠它了

USACO竞赛2月赛真题解析，所有组别题目超全汇总