USACO1月考题新鲜出炉！白银组别考情分析

2024年1月USACO月赛已经完美落下帷幕，白银级别的同学感觉考题如何呢？USACO竞赛除了考察计算机语言的熟练运用，也考察学生计算机程序的考察，那么USCO竞赛白银级别考题怎么样？题目难度如何？考察了哪些考点？今天小编老师为大家详细介绍USACO竞赛1月赛，那么同时，如果发挥失常的学生也不要气馁，一起期待2月考试即可哦~

USACO 2024年1月白银组别考情分析

第1题

有q对(x,y)的输入，每对表示前1~x个数右边第一个比它们大的数必须在下标为y的位置，这句话还有一个隐藏含义就是第x+1到第y-1个数必须比前1~x个数的最大值要小，即第y个数比前y-1个数都要大(代码中称为前缀最大值)。

用一个前缀和数组pre_max[i]表示前i个数中的最大值，则a[y]至少为pre_max[y-1]+1。

现在从左往右遍历a[N]，分类讨论每一个a[i]的情况：

1.a[i]==0且位置i是前缀最大值，令a[i]=pre_max[y-1]+1

2.a[i]==0 且不是前缀最大值，根据贪心思路令a[i]=1 (字典序最小)

3.a[i]不为0，是第x+1到第y-1个数的其中一个，但是比前x个数要大，破坏了前缀最大值的要求，此时需要把之前的某个能改的值提高为a[i]

对全部a[N]修改完毕后，再重新for循环扫描一遍看看新的a[N]有没有冲突，有冲突输出-1

注意事项：这题有T个测试，每个输出最后不能带空格

第2题

以房间1为根节点的树。每次traversal相当于从根出发，沿着父子关系一直走，一个traversal的终点一定是一个叶节点，因此最小的traversal数必定为叶节点数量，可以用dfs得到，假设这个数量是k。

可以用树上DP来记录每个节点的子树拥有的叶节点数量，状态转移方程为dp[fa] += dp[child],则dp[1]就是整棵树拥有的叶节点数量

此时来看题目对potion的描述，每次traversal会在一个节点生成一个potion，下一次traversal前消失，而我们只会有k个(即dp[1]个)traversal。

因此实际上只需要考虑前k个potion。而由于potion是依靠traversal获取的，因此potion和traversal,也就是叶节点，是一对一绑定的。假设我们目前在某个节点p，从点p出发获得的potion数量不会超过点p的子树拥有的叶节点数量。我们再用一个树上DP，potion[p]表示点p的子树拥有的potion数量，状态转移方程为potion[fa] += potion[child]。统计完毕后再令potion[p] = min(potion[p], dp[p])。

potion[1]就是本题答案。

第3题

抽屉原理+同余性质

题目等价于N个数除以L最多只有3个不同的余数，根据抽屉原理，任意选择4个不同的数 ，必定至少有两个数a[i]和a[j]除以L的余数相同(即模L同余)。由同余的基本性质可知abs(a[i]-a[j])必定能被L整除。

因此本题只需要从a[N]中任选4个不同的数，枚举它们的两两差值(一共有 = 6 种)，对这6个数，枚举它们的所有因子fac，进行检验(看看a[1]到a[N]除以fac是不是最多只有3个余数)，符合要求则令ans+=fac。

课程目标：完成USACO的知识点的学习。通过系统地梳理，充分的练习熟悉考试的题型和难点重点，冲刺USACO竞赛高分

USACO初级班：适合计算机编程刚入门，语言基础薄弱，无比赛经验计划申请计算机专业的中学生；

USACO中级班：适合至少会一门计算机编程语言(推荐C++或Java)，算法基础一般，少量比赛经验的学生

USACO高级班：适合具有完善的计算机编程语言基础，有入门算法经验，一定比赛经验，如NOIP，USACO银组等的学生

目前，犀牛已在上海、北京、广州、深圳、苏州、杭州、南京、青岛、无锡、武汉、合肥、成都等多个城市开设校区，线上线下全面开班，提供国际竞赛、国际课程、语言培训、择校、留学一站式课程培训，致力于为每一家庭提供优质服务。