昨天晚上,USACO12月竞赛的成绩已经发布了,不知道大家考的怎么样呢?必果学院根据竞赛结果为大家整理了这份USACO竞赛解析,文章末尾还有完整版的赛题参考代码希望对Farmer John和他的Bessie,以及你们(当然最重要的是你们)有所帮助!

想要参加后续两轮竞赛的同学,
也可以扫描文章末尾小助手的二维码,
加入USACO备考群了解USACO课程,
全力冲刺Platinum

2019USACO成绩发布,内附独家赛题解析!

12月USACO竞赛结果

本轮竞赛,中国地区有1615人参加,相比2018年12月份的竞赛,参赛人数增加了777人。参赛人数的增加不仅体现在中国地区,美国地区的参赛人数也比去年增加了626人,由此可见,USACO竞赛的热度越来越高

2019USACO成绩发布,内附独家赛题解析!

(2019年12月竞赛结果)

2019USACO成绩发布,内附独家赛题解析!

(2018年12月竞赛结果)

从编程语言的使用中,也可以看出USACO越来越受到大家的重视。本轮竞赛使用C++11语言解题的人数远远超过了使用Java语言解题的人数。在有限的解题时间内,使用程序运行效率高的C++语言对于考生来说是非常有利的,目前也有越来越多的学生为了参加USACO,专门去学习C++语言。

2019USACO成绩发布,内附独家赛题解析!

(2019年12月竞赛解题语言分析)

2019USACO成绩发布,内附独家赛题解析!

(2018年12月竞赛解题语言分析)
赛题解析

Bronze赛题

01

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!
赛题解析
2019USACO成绩发布,内附独家赛题解析!
采用枚举法,列出(i,j)组合,观察每场比赛是否都优秀。

02

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!
赛题解析
2019USACO成绩发布,内附独家赛题解析!
采用枚举法,列出每个长度,检查是否合法。

03

 

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!
赛题解析
2019USACO成绩发布,内附独家赛题解析!
采用枚举法,列出每个排列,检查是否合法。

Silver赛题

01

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!
赛题解析
2019USACO成绩发布,内附独家赛题解析!
定义f(x)表示x个人,报号的人数,通过容斥原理,再对f(x)二分得到答案。

02

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!
赛题解析
2019USACO成绩发布,内附独家赛题解析!
蚂蚁爬杆问题,只考虑爬出左右边界牛的个数,就不需要考虑操作2的交换速度操作。

因为牛的相对位置不变,我们知道左边到达几个,右边到达几个,就可以知道当前时间到达的牛的权值和。

第二问,经过时间T,通过排名的相对位移来测算碰撞次数。

03

 

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!
赛题解析
2019USACO成绩发布,内附独家赛题解析!
判断某条链上是否有某种奶牛,假定根为O,将这条链AB拆成两条链 OA和OB 在减去两倍的LCA(A, B),LCA是树上两点最近公共祖先,使用最快的ST表法 O(nlog(n))预处理 O(1)查询。

假定 cnt[A][0]是 A到O H牛的个数 cnt[A][1]是 A到O G牛的个数,那么AB链上H牛的个数是cnt[A][0] + cnt[B][0] – 2 * cnt[fa[LCA(A,B)][0]

 

Gold赛题

01

 

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!
赛题解析
2019USACO成绩发布,内附独家赛题解析!
考虑以下dp方程,dp[i][j]表示跑到i点最小的一个流时j的最小代价。

现假定有一条边 i v f c,那么dp[v][min(f, j)] = min(dp[v][min(f, j)], dp[i][j] + c),这个方程类似于最短路。

通过在dp方程上跑最短路算法获得结果。

02

 

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!
赛题解析
2019USACO成绩发布,内附独家赛题解析!
判断某条链上是否有某种奶牛,假定根为O,将这条链AB拆成两条链 OA和OB 在减去两倍的LCA(A, B),LCA是树上两点最近公共祖先,使用最快的ST表法 O(nlog(n))预处理 O(1)查询。

我们假定 cnt[A][0]是 A到O H牛的个数 cnt[A][1]是 A到O G牛的个数,那么AB链上H牛的个数是cnt[A][0] + cnt[B][0] – 2 * cnt[fa[LCA(A,B)][0]

将询问离线到三个点上 dfs查询即可 。

03

 

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!
赛题解析
2019USACO成绩发布,内附独家赛题解析!

从i跑到j的最小代价通过floyd算法松弛。

考虑一种dp,dp[i]表示考虑到第i个字符 前面的都合法的最小代价。

dp[i] = min(dp[j] + str[j + 1…i]的字符都变成同一个字符的代价) (i – j >= k)

这样朴素的dp复杂度是O(n^2*m)

发现这个dp值是从前缀转移过来的,通过前缀和优化可以优化到O(nm)

Platinum赛题

01

 

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!
赛题解析
2019USACO成绩发布,内附独家赛题解析!
考虑这样的区间dp,dp[l][r]表示这个区间完全被选中能获得的最大值。

转移中需要辅助数组

lma[l][r]表示(l,r)的所有子区间中dp的最大值

rma[l][r]表示(l,r)的所有子区间中dp的最大值

ma[l][r][k]表示能被区间[l,r]完全包含且能吃到点k的牛中权值最大的一头。

按照区间dp的经典套路转移复杂度O(n^3)

02

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!
赛题解析
2019USACO成绩发布,内附独家赛题解析!
如果给以x为根的子树染上颜色c。

假如这颗子树都没有颜色c,那么这颗子树每个点权值都加一,假如有染色,那么以其染色子树的跟删除,直到以x为根的子树没有颜色c,如此,每个染色操作至多被删除一次。

权值加一的操作,通过dfs序剖分后使用线段树维护。

这里还有两个子问题:

1.如果某次染色操作,其祖先已被染该颜色,该次染色无效 ;

2.怎么维护某种颜色下,有多少子树被染色。

这两个子问题都可以用set维护 。

03

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!

必果学院学生战绩

在本轮竞赛中,必果学院的学员们都取得了非常好的成绩,两名学生晋升到Platinum,三名学生晋升到Gold,三名学生晋升到Silver

 

余同学

等级:Platinum

分数:762

Tiger

等级:Platinum

分数:360

Cathy

等级:Gold

分数:1000

Helen

等级:Gold

分数:1000

Richard

等级:Gold

分数:806

Jacky

等级:Silver

分数:1000

Benjamin

等级:Silver

分数:1000

张同学

等级:Silver

分数:1000

赛题参考代码
想要各级赛题完整参考代码的同学,
可以扫描下方的微信二维码,
发送“Bessie”即可获得!

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!

2019USACO成绩发布,内附独家赛题解析!

USACO备考群
 

想要加入USACO备考群的小伙伴,
扫描上方的微信二维码
发送“USACO备考”即可入群,
群内不仅可以和其他同学讨论真题,
还可以享受更多USACO备考福利
希望这一次没有达到预期等级的你,
在一月份的考试中可以实现目标,
通过了记得要来我这里分享好消息哦!

 

2019USACO成绩发布,内附独家赛题解析!

也欢迎通过了的朋友们在下方留言处
分(xuan)享(yao)!

 

2019USACO成绩发布,内附独家赛题解析!

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

更多理工科竞赛在这里:

  1. 丘成桐中学科学奖:http://www.biggerlab.com/free/88827e98dc/
  2. FBLA-Tech:http://www.biggerlab.com/contests/f45534ecc3/
  3. WWDC:http://www.biggerlab.com/contests/wwdc-2/
  4. APCS:http://www.biggerlab.com/courses/9ded87fd85/

0 条评论

发表评论

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

error: Content is protected !!