​USACO竞赛难度很大吗 金牌选手说使用C++比Java解题更有利

对于一些想要申请优质大学计算机专业的同学们来说，手握USACO竞赛的奖项绝对可以在申请中秒杀众人。但是每年都会有很多同学们来问我们USACO竞赛难度很大吗？今天就用真题给同学们讲讲USACO竞赛难度到底是什么样的。

以下试题皆来自于2019年的真题

Bronze赛题

这题采用枚举法，列出(i,j)组合，观察每场比赛是否都优秀。

赛题解析：这道题还是采用枚举法，列出每个长度，检查是否合法。

赛题解析：采用枚举法，列出每个排列，检查是否合法。

Silver赛题

赛题解析：定义f(x)表示x个人，报号的人数，通过容斥原理，再对f(x)二分得到答案。

赛题解析蚂蚁爬杆问题，只考虑爬出左右边界牛的个数，就不需要考虑操作2的交换速度操作。因为牛的相对位置不变，我们知道左边到达几个，右边到达几个，就可以知道当前时间到达的牛的权值和。第二问，经过时间T，通过排名的相对位移来测算碰撞次数。

赛题解析：判断某条链上是否有某种奶牛，假定根为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赛题

考虑以下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方程上跑最短路算法获得结果。

判断某条链上是否有某种奶牛，假定根为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查询即可 。

从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赛题

考虑这样的区间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)

如果给以x为根的子树染上颜色c。假如这颗子树都没有颜色c，那么这颗子树每个点权值都加一，假如有染色，那么以其染色子树的跟删除，直到以x为根的子树没有颜色c，如此，每个染色操作至多被删除一次。权值加一的操作，通过dfs序剖分后使用线段树维护。

这里还有两个子问题：

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

2.怎么维护某种颜色下，有多少子树被染色。这两个子问题都可以用set维护 。

从以上的真题中我们能够看出如果使用C++11语言会比Java语言更简单有效的解题。因为在有限的解题时间内，使用程序运行效率高的C++语言对于考生来说是非常有利的。

竞赛是进入知名大学的关键助力之一。纵观橡沐今年113位牛剑录取的学员，大部分学员手里都握着各种竞赛奖项：AMC，UKCHO，BBO等等。能申请牛剑G5的学员成绩都不会差，只有竞赛、文书、背景提升这样的软实力才能拉开差距，2021年上半年就有一大波权威国际竞赛，如果你还不知道从哪里开始，就点击报名【橡沐竞赛复习班】，让知名大学海归竞赛导师带你选择最适合自己、最有利于申请的竞赛，高效梳理知识点，训练考试技巧，介绍联想、类比、归纳、转化、试误等答题技巧。

点击

计算机零基础 如何复习USACO竞赛

USACO比赛难度高吗？用一道真题解析告诉你

查看更多USACO竞赛信息。