花
注意到这个距离的定义类似曼哈顿距离,只是把 $+$ 变成了 $-$
联想到曼哈顿距离转切比雪夫距离,我们发现把坐标 $(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)$。