2024年USACO竞赛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。

1题

考察算法：二分，观察性质

首先假设当前在x轴朝向上行走，什么时候会转向到y轴?

我们发现当且仅当当前道路距离下一条道路是奇数距离的时候会转向

于是我们可以考虑去二分转向的次数，计算出在当前转向次数下运动的距离，判断它是否小于等于题目给出的运动距离

代码实现较为复杂，需要注意细节

时间复杂度: $O((n+q)*log)

2题

考察算法：动态规划

和银组第一题类似

定义$i$这个位置是前缀最大值当且仅当$a[i]>a[j]$ (for all $1\le j

我们会发现对于某个$(a[i],h[i])$相当于要求$[a[i]+1,h[i]-1]$这一段不能是前缀最大值，$h[i]$这个位置必须是前缀最大值

最终我们将相同情况的序列合并在一起，那么就是有最多$3*Q$段的序列(每一段内部要么要求一定是前缀最大值/一定不是前缀最大值/没有要求)，求最终合法的方案数

定义$dp[i][j]$代表当前考虑到前$i$段数，选的数的最大值是$j$的方案数

假设当前这一段序列长度为$len$

当一定是前缀最大值时:

$dp[i][j]=\sum_{k=1}^{j-1} dp[i-1][k]$

当一定不是前缀最大值时:

$dp[i][j]=dp[i-1][j]*j^{len}$

当没有要求时：

$dp[i][j]=dp[i-1][j]j^{len} + \sum_{k=1}^{j-1} dp[i-1][k](j^{len} -(j-1)^{len})$

时间复杂度: $O(qclog)$

3题

考察算法：二分

注意到分给Bessie自己的数越多答案相应的会越大，但是会越容易满足题目限制

所以我们考虑去二分 分给Bessie的个数$mid$

那么它们分别被加入序列的时间就是$mid, mid + (mid-1) ,... , mid+...+1$

显然我们比较希望尽量靠后的数能被加入到Bessie的序列中，所以对于每一个加入序列的时间我们可以贪心的去找到第一个大于当前时间且没有被插入到序列中的数，将它插入到序列中

这个过程可以用类似于双指针的思想来优化

最终$min(数字最大值,mid*(mid+1)/2)$就是我们的答案

时间复杂度: $O(n*log)$