蝶梦 题解

2019-03-31 12:34:28 By skyline

注意到这个距离的定义类似曼哈顿距离,只是把 $+$ 变成了 $-$

联想到曼哈顿距离转切比雪夫距离,我们发现把坐标 $(x,y)$ 变为 $((x+y)/2,(x-y)/2)$ 后,两点之间的距离变为它们横坐标/纵坐标差值的较小值。

把横/纵坐标相同的并起来,分别沿着横坐标/纵坐标扫一遍,用每个横/纵坐标和之前一个距离不为 $0$ 的坐标的差更新最小值 再用同样方法扫一遍更新最小值的个数。

实现这种做法的最优复杂度是 $\Theta(n)$。

考虑操作的性质其实是一某种方式遍历树花费的总距离,所以最小值是 $2$ 倍边数减去从 $1$ 出发最长的一条链长度(即根深度为 $0$ 定义下的树的深度)。

再考虑方案数,注意到进入一颗子树后必须经过所有节点才能出来(才能保证最小)。

考虑树形 DP,记录:进入一个子树经过所有节点再出来 和 进入一个子树经过所有节点 的方案数。

同时dp记录,进入一个子树经过所有节点再出来 的方案数的逆元,去掉一个快速幂的 $\log$。

时间复杂度 $\Theta(n)$。

这道题等价与问你有多少组不同的不下降序列,最小值不小于 $x$,和为 $n$。

取 $m=\sqrt n$,把每组序列拆成 $2$ 部分,分别为不大于 $m$ 的数和大于 $m$ 的数。

先计算对于任意 $i\le n$,有多少组不同的不下降序列,满足最小值不小于 $x$,最大值不大于 $m$,和为 $n$。直接背包 DP 即可。

再计算对于任意 $i\le n$,有多少组不同的不下降序列,最小值不小于 $\max(x,m+1)$,和为 $n$。

考虑 $dp(i,j)$ 表示有多少组不同的不下降序列,最小值不小于 $\max(x,m+1)$,和为 $n$,长度为 $j$。

$dp(i,j)$ 向 $dp(i+j,j)$(每个数 $+1$)和 $dp(i+\max(x,m+1),j+1)$(头上添加一个数 $\max(x,m+1)$)转移即可。

最后将 $2$ 部分的答案进行卷积,即得到最终答案。

时间复杂度 $\Theta (n\sqrt n)$。

评论

avatar
duyi
orzorz
avatar
skyline
彩蛋:把5个字连起来是什么呢?

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。