USACO1月的竞赛结果已经发布了

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

本文福利

扫描小助手二维码即可领取

USACO赛题完整版参考代码和竞赛资源包哦!

此外,必果学院还有USACO备赛群等你加入!

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛结果

本轮竞赛,中国地区共有1132人参加,相比于2019年12月比赛的参赛人数有所减少。在编程语言的选择上,C++11仍然是最受欢迎的语言。在有限的解题时间内,使用程序运行效率高的C++语言对于考生来说是非常有利的,目前也有越来越多的学生为了参加USACO,专门去学习C++语言。

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

(2020年1月USACO参赛人数)

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

(2019年12月USACO参赛人数)

USACO1月赛题解析

Bronze赛题

01

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
赛题解析
USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
每次输出前输出后是否会超过k个字符

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

02

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
赛题解析
USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
确定排列的第一个数后,整个序列都会确定

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

03

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
赛题解析
USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
最快的走法是将全路程分为两段:

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

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

需要注意:

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

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

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

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

Silver赛题

01

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
赛题解析
USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
最多的k/2篮不必太多

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

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

然后计算答案即可

02

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
赛题解析
USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
答案是具有单调性的

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

二分答案即可

03

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
赛题解析
USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
通过倒着加边发现:任何点可以通过已经加的边任意交换位置

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

使用并查集维护连通性

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

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

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

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

Gold赛题

01

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
赛题解析
USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
最多1000天后,不论到达哪一个城市,收获的都是负值

对1000天进行dp计算即可

02

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
赛题解析
USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
求出对于每一个子区间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月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
赛题解析
USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
先将点按二维坐标排序

有一个显然的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月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
赛题解析
USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
在同层之间存在一些等效点

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

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

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

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

02

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
赛题解析
USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包
考虑一种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月竞赛成绩发布,内附赛题参考代码和竞赛资源包

在本轮竞赛中,

必果学院的学员们都取得了非常好的成绩,

四名学生晋升到Platinum,

四名学生晋升到Gold,

四名学生晋升到Silver

 

USACO1月竞赛成绩发布,内附赛题参考代码和竞赛资源包

 往期推荐 

🔗

必果资讯|热门理工竞赛

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

201912月USACO赛题解析

国际理工竞赛集训|USACO, APCS, WWDC等你来!

你和斯坦福之间只差一次WWDC

FBLA-Tech|全球顶级商业•科技赛事来袭!
2020年APCS备考群,独家必看资料放送!

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

U.S. News2020全球大学排名+理工方向专业排名

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

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


0 条评论

发表评论

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

error: Content is protected !!