USACO银组试题解析，不同年级USACO备考规划介绍！

有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个测试，每个输出最后不能带空格

以房间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]就是本题答案。

抽屉原理+同余性质

题目等价于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。