[题解] [Mivik 的萌新赛 & Chino 的比赛 2020] Galgame

[题解] [Mivik 的萌新赛 & Chino 的比赛 2020] Galgame

定义两棵二叉树的大小关系:

  • 若它们皆为空,则相等;
  • 若它们的大小不同,则大小更小的更小;
  • 若它们的左子树不同,则左子树小的更小;
  • 否则其大小关系等价于它们右子树的大小关系。

给你一棵二叉树,问有多少二叉树比它小。

$1\le n\le 10^6$

原题链接


思路

Subtask 1

暴力枚举也许能过。

Subtask 2

记 $f(x)$ 为和 x 这一二叉树结点数相同但更为无趣二叉树数目,则有:

$$
f(x)=f(lson(x))C_{size(rson(x))}+f(rson(x))+\sum_{i=0}^{size(lson(x))-1}C_i C_{size(x)-i-1}
$$

其中 $C_n$ 为卡特兰数。然后我们 $O(n^2)$ 计算即可。

满分做法

我们对上面的做法做一个优化:我们先预处理出卡特兰数列的自卷积,然后对于 $size(lson(x))\le size(rson(x))$ 的情况,我们和上面一样暴力算;然后对于 $size(lson(x))>size(rson(x))$ 的情况,我们从预处理出的卷积里面减去多算的部分。然后,注意到卡特兰数列的自卷积等于它本身(偏移了一位),因此我们连卷积都不需要计算了。具体的,设卡特兰数列的生成函数是 $H(x)$,我们有 $H(x)^2\cdot x+1=H(x)$,我们所需要的卡特兰数自卷积 $F(x)=H(x)^2$,那么有 $[x^i]F(x)=[x^i]\left(\frac{H(x)-1}{x}\right)=[x^{i+1}]H(x)$。

这样实际上是对的。我们对每一个点考虑它会对时间复杂度产生多大贡献:自下而上地,如果一个点贡献所在的子树的 $size$ 是我们决定计算的部分,那么整棵树的大小必定大于等于这个点所在子树大小的两倍,也就是说,一个点如果想对时间复杂度产生 $1$ 的贡献,则其所在子树大小至少会增大 2 倍。因此一个点最多对时间复杂度产生 $\log n$ 的贡献,则总时间复杂度最劣为 $O(n\log n)$。

代码

mivik.h

代码

作者

Mivik

发布于

2020-12-04

更新于

2021-05-31

许可协议

评论