USACO2020年1月的竞赛已经结束了

不知道大家考的怎么样呢?

理工君第一时间帮大家整理了

这次竞赛的赛题以及独家解析

希望对Farmer John和他的奶牛,

以及你们(当然最重要的是你们)

有所帮助!

 

USACO1月赛题解析,Farmer John说让你点进来看看

Bronze赛题

01

USACO1月赛题解析,Farmer John说让你点进来看看

USACO1月赛题解析,Farmer John说让你点进来看看
赛题解析
USACO1月赛题解析,Farmer John说让你点进来看看
每次输出前输出后是否会超过k个字符

输出如果超过k个字符进行换行输出即可

02

USACO1月赛题解析,Farmer John说让你点进来看看

USACO1月赛题解析,Farmer John说让你点进来看看
赛题解析
USACO1月赛题解析,Farmer John说让你点进来看看
确定排列的第一个数后,整个序列都会确定

枚举第一个数检查是否是一个排列即可

03

USACO1月赛题解析,Farmer John说让你点进来看看

USACO1月赛题解析,Farmer John说让你点进来看看

USACO1月赛题解析,Farmer John说让你点进来看看
赛题解析
USACO1月赛题解析,Farmer John说让你点进来看看
最快的走法是将全路程分为两段:

第一段为提速阶段每秒速度加1;

第二段为减速阶段每秒速度减1

需要注意:

当某个速度<最后的限定速度时,这个速度只呆一秒

当某个速度>=最后的限定速度时,这个速度应该呆两秒(即加速阶段一秒 减速阶段一秒)

当按照最快的走法求得的sum > k时:

找到最快的sum-k秒,速度统一减一即可均衡,最短时间相同

Silver赛题

01

USACO1月赛题解析,Farmer John说让你点进来看看

USACO1月赛题解析,Farmer John说让你点进来看看
赛题解析
USACO1月赛题解析,Farmer John说让你点进来看看
最多的k/2篮不必太多

枚举我们能拿到的篮子中的最大值

显然给第一个人的篮子内容不应该大于这个值

然后计算答案即可

02

USACO1月赛题解析,Farmer John说让你点进来看看

USACO1月赛题解析,Farmer John说让你点进来看看
赛题解析
USACO1月赛题解析,Farmer John说让你点进来看看
答案是具有单调性的

枚举天数和当前应该给的牛奶数

二分答案即可

03

USACO1月赛题解析,Farmer John说让你点进来看看

USACO1月赛题解析,Farmer John说让你点进来看看

USACO1月赛题解析,Farmer John说让你点进来看看
赛题解析
USACO1月赛题解析,Farmer John说让你点进来看看
通过倒着加边发现:任何点可以通过已经加的边任意交换位置

在每次加边的时候需要判断是否合法

使用并查集维护连通性

如何快速的判断是否合法:

点是否合法的状态只会随着边增加,从不合法变为合法,而不会从合法变为不合法

所以每次从最左边的不合法的点开始判断整体是否变为合法

这个判断函数整体的复杂度是均摊的O(n)

Gold赛题

01

USACO1月赛题解析,Farmer John说让你点进来看看

USACO1月赛题解析,Farmer John说让你点进来看看
赛题解析
USACO1月赛题解析,Farmer John说让你点进来看看
最多1000天后,不论到达哪一个城市,收获的都是负值

对1000天进行dp计算即可

02

USACO1月赛题解析,Farmer John说让你点进来看看

USACO1月赛题解析,Farmer John说让你点进来看看
赛题解析
USACO1月赛题解析,Farmer John说让你点进来看看
求出对于每一个子区间3sum的个数:

令dp[i][j]表示第i个数和第j个数必选剩下一个选中间的数的方案数

通过差分可以求得任意一个子区间3sum的个数

使用递归来求dp[i][j]

求一次的复杂度是O(n^2)

总体复杂度看似是O(n^2log(n))

但其实T(n) = n^2

总体复杂度是 T(n) + T(n / 2) * 2 + T(n / 4) * 4 + T(n / 8) * 8….

03

USACO1月赛题解析,Farmer John说让你点进来看看

USACO1月赛题解析,Farmer John说让你点进来看看
赛题解析
USACO1月赛题解析,Farmer John说让你点进来看看
先将点按二维坐标排序

有一个显然的O(P^2)做法:计算到达当前虫洞起点数

枚举每个虫洞观察是否可达且最小

通过使用线段树优化这个过程达到O(Plog(P))

假定dp[i]表示到达dp[i]的最短距离

dp[i] = min(dp[j] + dis(i, j)) dis(i, j)表示j虫洞的终点到i虫洞的起点的距离

这是个和i、j点位相关的函数,无法用数据结构维护

把这个函数拆成 dp[i] = min(dp[j] – ed_x[j] – ed_y[j]) + st_x[i] + st_y[i]

将min中的值扔到线段树中即可

Platinum赛题

01

USACO1月赛题解析,Farmer John说让你点进来看看

USACO1月赛题解析,Farmer John说让你点进来看看
赛题解析
USACO1月赛题解析,Farmer John说让你点进来看看
在同层之间存在一些等效点

等效点的定义是:当其中某个点加了水以后其他点必定也有水

需要扣出整张图的等效点,建立转移边以后,得出一张DAG

在这张DAG上跑dp即可获得答案

我们使用并查集来得出等效点

02

USACO1月赛题解析,Farmer John说让你点进来看看

USACO1月赛题解析,Farmer John说让你点进来看看
赛题解析
USACO1月赛题解析,Farmer John说让你点进来看看
考虑一种O(n*k^2*log(n))的做法

实际复杂度是3e8乘一个常数,此做法能否通过取决于常数的大小

本题时限2s,常规写法大约3s左右,通过一系列卡常写法可以卡进1s

用递归的思想解决问题:

假设当前解决到区间[l,r]其终点为m

我们从中点向两边延申

转移方程dp[x][i][j]

当x在[l,m]时表示[x..m]中以i为起点、j为终点的非递减子序列个数

当x在[m+1,r]时表示[m+1..x]中以i为起点、j为终点的非递减子序列个数

当询问[rl,rr]跨过这个中点时,合并dp[rl][1…k][1…k] 和 dp[rr][1…k][1…k]来求解这个询问

如果被[l,r]包含的询问不跨越中点则向[l,m]和[m+1,r]继续递归

计算dp数组的复杂度时O(n*k^2),由于递归会有log(n)层

总体复杂度O(n*k^2*log(n))

03

USACO1月赛题解析,Farmer John说让你点进来看看

以上就是USACO2020年1月的赛题解析,
想要领取完整版参考代码的同学,
 

USACO1月赛题解析,Farmer John说让你点进来看看

USACO1月赛题解析,Farmer John说让你点进来看看

扫描下方的微信二维码,
添加理工留学君为好友,
发送“USACO1月”即可。

USACO1月赛题解析,Farmer John说让你点进来看看

希望你们都能在竞赛中达到自己期望的等级!

USACO1月赛题解析,Farmer John说让你点进来看看

必果资讯|热门理工竞赛

USACO官网:http://www.usaco.org/

NOIP竞赛回归|CCF关于恢复NOIP竞赛的公告

NYU不会拒绝一个一件事坚持了10年的你

南加大,对不起,我要去NYC设计游戏了。

史上最全理工夏校信息汇总(一)|内附申请相关材料

U.S. News2020全球大学排名发布,内附理工方向专业排名

USACO12月赛题解析

竞赛介绍|FBLA-Tech:结合科技与商业的完美契机!

帮我点个“在看”再走吧!


0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

error: Content is protected !!