【福利】独家首发USACO 3月赛US Open全部组别赛题解析

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

截至美东时间周二上午8点,US Open赛结束,至此,USACO 2019-2020赛季正式落下帷幕。满分同学会当场晋级,没有当场晋级的同学可以耐心等待一周之内出成绩。

铂金级满分通过记录(最高级别

【福利】独家首发USACO 3月赛US Open全部组别赛题解析
【福利】独家首发USACO 3月赛US Open全部组别赛题解析
【福利】独家首发USACO 3月赛US Open全部组别赛题解析

本次US Open赛事题面非常与时俱进,奶牛的世界也爆发了新冠病毒COWVID-19,如有的让你帮忙计算社交距离,有的让你帮忙追踪0号病人(牛),出现了不少高质量的题目。更多内容,请参考下文解析。

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

以下内容是四大级别的赛题解析,供同学们参考交流。想要咨询参赛和备考冲刺计划的同学,可以扫描文末二维码,添加老师微信获取。

 

(题解内容为图片,可点击放大查看)

 

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

01 Social Distancing I

题目大意

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

题目解析:

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

02 Social Distancing II

题目大意

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

题目解析:

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

03 Cowntact Tracing

题目大意

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

题目解析:

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

01 Social Distancing

题目大意

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

题目解析

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

02 Cereal

题目大意

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

题目解析:

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

03 The Moo Particle

题目大意

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

题目解析:

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

01 Haircut

题目大意

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

题目解析:

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

02 Favorite Colors

题目大意

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

题目解析:

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

03 Exercise

题目大意

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

题目解析:

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

01 Sprinklers 2: Return of the Alfalfa

题目大意

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

题目解析:

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

02 Exercise

题目大意

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

题目解析:

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

03 Circus

题目大意

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

题目解析:

【福利】独家首发USACO 3月赛US Open全部组别赛题解析

2019-2020赛季

往期题解

【福利】全球首发USACO Dec月赛全部组别试题解析

【福利】独家首发USACO 1月赛全部组别试题解析

【福利】独家首发USACO 2月赛全部组别赛题解析

USACO 2020 US Open赛题解析

 
截止到今晚8:00

USACO 2020 US Open已经结束了,

不知道同学们考的怎么样呢?

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

理工君第一时间帮大家整理了
这次竞赛的赛题以及独家解析
文章末尾还有完整版的赛题参考代码
希望对Farmer John和他的Bessie,
以及你们(当然最重要的是你们)
有所帮助!
 

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

Bronze赛题

01

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
赛题解析
USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
这道题我们将所有的空隙挖出来,考虑所有的情况即可

02

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
赛题解析
USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
首先我们要找出题目中R的最大值

R表示疾病的传播半径 如果两个人距离小于R即会被传染

我们发现如果相邻的两个人 一个人传染一个人不传染 那么R不应该大于这两个人的距离

当求出最大的R以后 我们即可求出答案

03

 

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
赛题解析
USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
枚举零号感染者和K即可

Silver赛题

01

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
赛题解析
USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
经过观察 我们发现题目所求的D具有单调性

即D越小越容易符合题意

二分答案即可

02

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
赛题解析
USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
我们从后往前插入

然后每个数只会挪动两次位置

所以总体复杂度O(n)

03

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
赛题解析
USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
我们按将x和y从大到小排序

然后确保了 后出现的x更小

然后进行块合并即可

Gold赛题

01

 

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
赛题解析
USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
我们从小到达的插入数据

我们发现 当我们插入一个数时 前面还没有插的位置 此后一定比当前数大

所以使用树状数组统计即可

02

 

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
赛题解析
USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
这是一个并查集问题

我们发现一个点的儿子都需要合并

我们假设x y需要合并 那么他们的儿子也需要合并 这个过程时O(n^2)的

我们可以用类似spfa的技巧将这个过程优化到O(n)或者启发式的思想优化到O(nlog(n))

03

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
赛题解析
USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
考虑每个素数的贡献

计算答案即可

 

Platinum赛题

01

 

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
赛题解析
USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
我们发现一个我们的轮廓线每弯折一次 那么就会有一个点被确定

我们dp即可

我们设计dp[i][j][0..1]的状态

dp[i][j][0] 表示从dp[i – 1][j]即从上面转移的方案数的和

dp[i][j][1] 表示从dp[i][j – 1]即从左边转移的方案数的和

进行转移即可

我们在状态中只考虑当前轮廓线的最后一个点和到达最后一个点的方式

通过这样的方式消除前效性

02

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
赛题解析
USACO 2020 US Open赛题解析|Farmer John说让你点进来看看
对于一个排列,循环节为t,出现p次,贡献t^p,因此目标是统计每种循环节的出现次数

由于循环节范围太大,对t分解质因数 t = p1^q1 * p2^q2 * … * pk^qk 贡献可以分解成质因数p的q次方的贡献。

p的q次方的贡献 = q次p的贡献  因为p^q除1外刚好q个约数,可以等效算q次p的贡献

统计循环节是p^q倍数的排列数 = N! – 循环节没有p^q倍数的排列数

循环节没有p^q倍数的排列数 可以用动态规划解决

03

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

USACO 2020 US Open赛题解析|Farmer John说让你点进来看看

 

美国高中计算机奥林匹克(USACO)介绍

现在,计算机编程似乎已经成为大家生活中必备的技能了。甚至很多小学生从一年级开始就已经会用Python编游戏了。很多同学在选专业的时候也都会考虑double一个计算机来拓展以后就业的机会。因此,这里就来给大家介绍一下美国最有名的计算机竞赛吧!

USACO

USACO(USA Computing Olympiad)

是美国最具认可度和参与度最高的计算机竞赛,用于选拔美国参加全球信息奥林匹克竞赛(IOI)的国家队。全球的参赛者都可以通过参加网上的三场竞赛,晋级铜奖、银奖、金奖和白金奖四个等级。(感觉有点像打王者哈哈哈)虽然,最后只有美国公民或者绿卡持有者才有机会参加训练营或者最表美国队参加IOI,但是你在USACO的等级可以充分证明你的编程实力,而且也是很红的训练机会哦!

2019-2020 比赛时间

Dec 13-16: First Contest 第一轮竞赛

Jan 17-20: Second Contest 第二轮竞赛

Feb 21-24: Third Contest 第三轮竞赛

Mar 27-30: US Open 美国总决赛

May 21-30: Training Camp 训练营 16-24人

Jul 19-26: IOI 2020 in Singapore 全球信息奥林匹克竞赛(新加坡) 4人

任何人都可以参加USACO的前三场比赛和美国总决赛并完成晋级/获得奖项,但是只有美国公民或者绿卡持有者可以参加训练营和最终代表美国队参加IOI。

时。

报名方法

随时可以注册账号报名,在比赛时间开始时登陆账号开始比赛即可。

官网链接:http://www.usaco.org/index.php

比赛形式

USACO的比赛时间和形式比较随性,参赛者只要在规定的时间里登陆账号,下载题目,并在3-4小时内提交答案就可以。虽然比赛并没有任何形式的监考和限制,依旧希望参赛的同学们能自觉地遵守考试规则:)

一场比赛通常由3-4个问题,你可以使用C,C++,Pascal,Java,Python中的任意一种语言解题。评分方式是网站自动判定你的程序在规定的时间内所能正确解答的Test Case个数,所以有些时候需要使用较为巧妙的算法。

当你提交你的程序之后,每个Test Case都会获得反馈,绿色代表成功,红色代表失败。其中失败又分为很多种。X 代表答案错误, T 代表超时, ! 代表运行错误或者超出内存限制, E 代表输出文件为空, M 代表没有输出文件.

详细规则请见:

http://www.usaco.org/index.php?page=instructions

USACO等级

青铜

参赛资格:一进入USACO注册账号即为铜级。

难度等级:铜级考试只要基本编程常识,会至少一种编程语言。铜级的编程限制时间还是够用的,大部分初次参赛的选手都能在第一次考试中晋级白银级。

白银

参赛资格:通过青铜级比赛的选手。

难度等级:需要基本的问题解决能力和简单算法(例如:贪心算法,递归搜索等),还需了解基础数据结构。从白银级开始,选手需要寻找更好的算法才能使程序在规定时间内跑完。

黄金

参赛资格:通过白银级比赛的选手。

难度等级:需要有一定的算法基础,理解一些抽象的方法(例:最短路径,动态规划),并且对数据结构有比较深的了解。

白金

参赛资格:通过黄金级比赛的选手。

难度等级:需要有很高的编程基础,对算法有深入的了解。部分比赛问题最后的优化方案,可能不只一个,得出的答案也不只一个。

每次比赛,选手都可以向更高的级别发起挑战。在比赛窗口开放的三天时间内,选手可以选择任意时间开始比赛。如果拿到了满分,可以在比赛窗口关闭之前就晋级到下一级。升级了之后,只要比赛窗口还没有关闭,可以继续向下一个等级进发。没能拿到满分的同学需要等到比赛窗口关闭,等待晋级分数线,才能决定是否晋级。