USACO什么难度 不会编程没有算法知识也能参加

USACO竞赛在美国以及世界上有着极高的认可度，很多没有编程经验的同学们都会问我们USACO什么难度，有人将AMC与USACO进行比较，很多理科类美国大学都会要求申请者有AMC成绩。认为在申请大学时，USACO能与AMC起到类似作用。所以同学们了解usaco的含金量了吧，下面用真题给大家讲讲USACO什么难度吧！ 

题目描述

一种新型疾病，COWVID-19，开始在全世界的奶牛之间传播。Farmer John 正在采取尽可能多的预防措施来防止他的牛群被感染。Farmer 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 = ......

以上就是本期的USACO竞赛的真题，同学们看完真题了解了USACO难度了吗？如果您还想了解更多需求的话，欢迎您前来橡沐，橡沐有更多的精英在等着你，马上就要开赛了，赶紧点击【预约试听】报名吧！

点击计算机零基础 如何复习USACO竞赛

美国大学对USACO 竞赛的认可度怎么样查看更多USACO竞赛的信息。