USACO 19DEC Platinum 总结

这套题被拿来做 NOI 模拟，要是 NOI 这个难度，大概人均 AK（逃 ### [Greedy Pie Eaters](https://www.luogu.com.cn/problem/P5851) 这道题题意并不复杂，因此我们猜想这道题也不太难。 结果我考试时就放飞自我，证了一个假的结论，认为一定存在一种合法的方案，使得牛的左端点单调不减，那么右端点一定单调递增。实际上这是完全不正确的，比如 $[1,5],[3,4]$ 两头牛是完全可以兼顾的。然而这个结论恰好能过样例，所以这题就爆 $5$ 了。 因此如果没有大样例，一定记得造数据对拍；即使有大样例，对期望得分比较高的题目也还是要造数据对拍。 正确的解法并没有证什么结论。由于 $n\le 300$，可以采用区间 dp；设 $f[i][j]$ 表示假设只有 $[i,j]$ 范围的食物，那么能够喂的牛的权值和的最大值。$f[i][i]$ 只能等于吃 $[i,i]$ 的牛的权值，而对于一般的区间 $[i,j](i<j)$，我们把最后一头牛拿出来，设它吃的第一个食物为 $k$（也就是，之前的牛都没有吃、但这一头牛吃了的食物中，下标最小值为 $k$），那么前面的牛要么吃 $[i,k-1]$ 的草，要么吃 $[k+1,j]$ 的草。 那么，考虑 $f[i][j]$ 时，我们得到了几个条件： - 前面的牛要么吃 $[i,k-1]$ 的草，要么吃 $[k+1,j]$ 的草（而且不能都吃，否则一定会顺手吃掉 $k$）。 - 最后一头牛一定要吃 $k$ - $i\le k\le j$，且所有的牛的区间都是 $[i,j]$ 的子集 根据这些条件，$f[i][j]$ 可以由 $f[i][k-1]$、$f[k+1][j]$ 加上一个区间 $[l,r]\ (i\le l\le k\le r\le j)$ 组成。 由于要取最大值，我们得到 $f[i][j]=\max(f[i][k-1]+f[k+1][j]+g[l][k][r])$，其中 $i\le k\le j$，且 $g[l][k][r]$ 表示所有区间 $[l,r]\ (i\le l\le k\le r\le j)$ 的最大权值。 $g$ 也可以简单地递推，$g[l][k][r]$ 要么来自 $g[l+1][k][r]$，要么来自 $g[l][k][r-1]$，要么就是一个区间 $[l,r]$。 这两个 dp 都应该按区间长度顺序做，时间复杂度都是 $\mathrm{O}(n^3)$。 有没有什么优化的方法呢？$g$ 数组可以使用滚动数组，$g$ 和 $f$ 一同计算，那么区间长度就是一个定值，可以省去 $r$ 这一维，这样整道题的空间复杂度是 $\mathrm{O}(n^2)$。随着空间的优化，时间常数也得到了极大的优化，这让我们再次体会到了“优化空间访问就是优化时间”这一句话的意义。 ### [Bessie's Snow Cow](https://www.luogu.com.cn/problem/P5852) 一道普通的树上信息维护题，最重要的是意识到撤销先前的修改至多进行 $m$ 次，因此撤销是可以承受的。 另外就是灵活运用 dfs 序。 ### [Tree Depth](https://www.luogu.com.cn/problem/P5853) 一道不错的计数题。 最简单的暴力可以直接拿到 $30$ 分，非常划算。 接下来 $n\le 20$ 的部分分，由于没有找到“深度”的性质，我尝试了一种“新的”思路（其实这个思路很常见，只是我从来没做过），用 dp 模拟暴力建树的过程。这里主要利用的性质是，向两边递归时可以将数列重新离散化，这样就归为 $n$ 稍小的子问题。结果由于逆序对数要大力枚举，这个 dp 的复杂度达到了 $\mathrm{O}(n^9)$，可能是我写过的复杂度最高的多项式级别 dp 了。不过实际上常数比较小，因此开 O2 可以通过 $n\le 20$ 的部分分。 接下来就需要找到“深度”的性质才能做了。事实上，$j$ 是 $i$ 的祖先，当且仅当 $i\sim j$ 这一段的最小值在 $j$ 处。这个性质可能在考场上能够通过一些稍大的例子来发现。这样，我们对于每对 $(i,j)$，计算 $j$ 是 $i$ 的祖先的排列的数量，求和就得到 $i$ 的答案。 如何计算满足 $i\sim j$ 这段的最小值在 $j$ 处，且逆序对数为 $k$ 的排列数量呢？这里又涉及到一个经典 dp，长度为 $n$、逆序对数为 $k$ 的排列的数量。用到的核心结论是，向一个长度为 $n$ 的排列的左端或右端添加一个元素（并重新离散化），产生一个长度为 $n+1$ 的排列时，能够增添的逆序对数量的值域是 $[0,n]$；并且任何一个排列都可以通过上述过程构造。 这样，我们采取的构造策略是，先构造 $i\sim j$ 这段，再向两边加数，形成最终的排列。 构造 $i\sim j$ 这段时，除了加 $j$ 时必须加一个最小的之外，其他的 $\vert j-i\vert$ 个数都没有限制；向两边加数是没有任何限制的。加 $j$ 时，如果 $j$ 在 $i$ 左端，那么加一个最小的数，逆序对数必须不变；如果 $j$ 在 $i$ 右端，那么加一个最小的数，逆序对数必须增加 $j-i$。 下面我们用 dp 来描述上面的过程。 $f[i][j]$ 表示要插入 $i$ 个元素，这些元素能产生逆序对的范围分别是 $[0,0],[0,1],\cdots,[0,i-1]$，总共产生 $j$ 个逆序对的方案数。$f$ 描述了构造 $i\sim j$（不包括 $j$）的过程，转移方程是 $f[0][0]=1,f[i][j]=f[i-1][j]+f[i-1][j-1]+\cdots+f[i-1][j-(i-1)]$ 。 $g[i][j]$ 表示要插入 $i$ 个元素，这些元素能产生逆序对的范围分别是 $[0,n-1],[0,n-2],\cdots,[0,n-i]$，总共产生 $j$ 个逆序对的方案数。$g$ 描述了构造剩下的数的方案数，$g[0][0]=1,g[i][j]=g[i-1][j]+g[i-1][j-1]+\cdots+g[i-1][j-(n-i)]$。 设 $\vert i-j\vert =d$。 1. 先插入 $d$ 个元素，假设产生了 $u$ 个逆序对，方案数是 $f[d][u]$； 2. 再插入 $j$，产生 $d$ 个或 $0$ 个逆序对； 3. 最后插入剩余的 $n-d-1$ 个元素，产生了 $v$ 个逆序对，方案数是 $g[n-d-1][v]$。 最终的逆序对数为 $k$，因此应该有 $u+v+d=k$ 或 $u+v=k$。 于是只要枚举 $u$，就可以知道 $v$，把方案数分别用乘法原理乘起来，最后求和即得到 $j$ 对 $i$ 的贡献。 从计算的过程我们知道，这个贡献只与距离和方向有关，因此进行预处理，需要时直接调用。计算 $f,g$ 的复杂度是 $\mathrm{O}(nk)$，预处理贡献的复杂度也是 $\mathrm{O}(nk)$，总复杂度 $\mathrm{O}(nk)$。