Home » 国际竞赛 » Details

2024年USACO1月月考题目出炉！白银组别考情分析

Category: 国际竞赛, 翰林严选, 计算机国际竞赛 Date: 2024年2月4日下午4:42

USACO计算机编程竞赛的1月月赛已经完美结束啦，这次没有晋级到自己心仪级别的同学也不要着急，接下来可以等待2月的月赛！

1月月赛白银组考了哪些内容？今天整理了1月USACO竞赛白银组别考情分析，希望对同学们接下来的USACO竞赛备考有所帮助。

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历年真题及参考书