Sweetlemon 的博客

Sweetlemon 的博客

USACO 19DEC Platinum 总结

posted on 2020-08-11 09:59:15 | under 总结 |

这套题被拿来做 NOI 模拟,要是 NOI 这个难度,大概人均 AK(逃

Greedy Pie Eaters

这道题题意并不复杂,因此我们猜想这道题也不太难。

结果我考试时就放飞自我,证了一个假的结论,认为一定存在一种合法的方案,使得牛的左端点单调不减,那么右端点一定单调递增。实际上这是完全不正确的,比如 $[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

一道普通的树上信息维护题,最重要的是意识到撤销先前的修改至多进行 $m$ 次,因此撤销是可以承受的。

另外就是灵活运用 dfs 序。

Tree Depth

一道不错的计数题。

最简单的暴力可以直接拿到 $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)$。