USACO美国计算机奥林匹克竞赛经典试题!

USACO美国计算机奥林匹克竞赛于1992年首次举办,距今已有30年的历史,是最负盛名的国际计算机竞赛之一。全球的参赛者都可以通过参加网上的三场竞赛,晋级铜奖、银奖、金奖和白金奖四个等级,今天小编大家来看看几道经典试题!

竞赛介绍

USACO(United States of America Computing Olympiad, 美国计算机奥林匹克竞赛) 是一项针对全世界所有的高中信息学竞赛选手的一项竞赛。开设目的是为每年夏季举办的国际信息学奥林匹克竞赛(IOI)选拔美国队队员。这项赛事不仅可以培养学生的算法和编程思维,好的竞赛成绩还能给孩子大学申请加分。由于有些编程题跟谷歌,脸书等顶级科技公司面试题类似,好的USACO竞赛成绩对孩子以后申请实习也大有裨益。

经典试题

2020USACO铜组第1题

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

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

最近两头奶牛新来到 John 的牛群,他需要决定将她们分配到哪两个之前空着的牛栏。请求出他如何放置这两头新来的奶牛,使得 D 仍然尽可能大。

John 不能移动任何已有的奶牛;他只想要给新来的奶牛分配牛栏。

2020USACO银组第2题

John 的奶牛们的早餐最爱当然是麦片了!事实上,奶牛们的胃口是如此之大,每头奶牛一顿饭可以吃掉整整一箱麦片。

最近农场收到了一份快递,内有 M 种不同种类的麦片(1≤M≤105)。不幸的是,每种麦片只有一箱!N 头奶牛(1≤N≤105)中的每头都有她最爱的麦片和第二喜爱的麦片。

给定一些可选的麦片,奶牛会执行如下的过程:如果最爱的麦片还在,取走并离开。

否则,如果第二喜爱的麦片还在,取走并离开。

否则,会失望地哞叫一声然后不带走一片麦片地离开。奶牛们排队领取麦片。对于每一个 0≤i≤N−1,求如果 Farmer John 从队伍中移除前 i 头奶牛,有多少奶牛会取走一箱麦片。

比赛时间

USACO分为月赛和公开赛。12月、1月、2月分别有3场月赛,3月举办公开赛。如果你是高一、高二的学生,可以参加任意一场考试,如果你正值高三,则可以报名12月的考试,抓住最后一次提升背景的机会。

【扫码联系老师领取报名表】

获取备赛计划,考前查缺补漏、重点冲刺

免费领取相关真题及解析,还有一对一学术活动规划!

翰林国际教育资讯二维码