截止到今晚8:00USACO这一轮的竞赛已经结束了,不知道同学们考的怎么样呢?必果学院第一时间帮大家整理了这次竞赛的赛题以及独家USACO赛题解析文章末尾还有完整版的赛题参考代码希望对Farmer John和他的Bessie,以及你们(当然最重要的是你们)有所帮助!
 

USACO独家赛题解析|Farmer John说让你点进来看看

Bronze赛题

01

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看
赛题解析
USACO独家赛题解析|Farmer John说让你点进来看看
采用枚举法,列出(i,j)组合,观察每场比赛是否都优秀。

02

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看
赛题解析
USACO独家赛题解析|Farmer John说让你点进来看看
采用枚举法,列出每个长度,检查是否合法。

03

 

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看
赛题解析
USACO独家赛题解析|Farmer John说让你点进来看看
采用枚举法,列出每个排列,检查是否合法。

Silver赛题

01

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看
赛题解析
USACO独家赛题解析|Farmer John说让你点进来看看
定义f(x)表示x个人,报号的人数,通过容斥原理,再对f(x)二分得到答案。

02

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看
赛题解析
USACO独家赛题解析|Farmer John说让你点进来看看
蚂蚁爬杆问题,只考虑爬出左右边界牛的个数,就不需要考虑操作2的交换速度操作。

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

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

03

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看
赛题解析
USACO独家赛题解析|Farmer John说让你点进来看看
判断某条链上是否有某种奶牛,假定根为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

 

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看
赛题解析
USACO独家赛题解析|Farmer John说让你点进来看看
考虑以下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

 

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看
赛题解析
USACO独家赛题解析|Farmer John说让你点进来看看
判断某条链上是否有某种奶牛,假定根为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

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看
赛题解析
USACO独家赛题解析|Farmer John说让你点进来看看

从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

 

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看
赛题解析
USACO独家赛题解析|Farmer John说让你点进来看看
考虑这样的区间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

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看
赛题解析
USACO独家赛题解析|Farmer John说让你点进来看看
如果给以x为根的子树染上颜色c。

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

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

这里还有两个子问题:

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

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

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

03

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看

赛题参考代码

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

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看

USACO独家赛题解析|Farmer John说让你点进来看看

USACO备考群

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

 

USACO独家赛题解析|Farmer John说让你点进来看看

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

 

USACO独家赛题解析|Farmer John说让你点进来看看

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

更多理工科竞赛在这里:

  1. APCS:http://www.biggerlab.com/courses/9ded87fd85/
  2. FBLA-Tech:http://www.biggerlab.com/contests/f45534ecc3/
  3. WWDC:http://www.biggerlab.com/contests/wwdc-2/

0 条评论

发表评论

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

error: Content is protected !!