今天给大家分享一道与社交距离相关的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双赢,点击预约试听【唯寻竞赛复习班】——
知名大学海归一线竞赛导师授课
精准匹配同一学力考生
对知识模块进行全面系统教学
扫清学习过程中的各种障碍
帮助学员构建思维模型
全面启发竞赛思维
激发国际课程热情
更多竞赛复习攻略点击