Nemlit 的博客

Nemlit 的博客

By a konjac

题解 CF1237E 【Balanced Binary Search Trees】

posted on 2019-10-18 17:26:03 | under 题解 |

首先我们要注意到一个性质:由于根与右子树的根奇偶性相同,那么根的奇偶性与 $N$ 相同

然后我们发现对于一个完美树,他的左右两个儿子都是完美树

也就是说,一颗完美树是由两棵完美树拼成的

注意到另一个性质:由于权值是一个排列,假设根节点为 $x$ ,那么左子树的范围是 $[1, x - 1]$ ,右子树为 $[x + 1, n]$

由于根节点和 $N$ 奇偶性相同,那么左子树的大小与 $N$ 的奇偶性相反,所以右子树大小为偶数

如果子树区间为 $[l, r]$ ,那么其实可以把它看成 $[1, r - l + 1]$ ,所以只和子树大小有关,和子树权值无关

手玩一波小数据:

当 $N=1$ 时,就是一个点

当 $N=2$ 时,二为根,一为根的左子树

当 $N=3/4$ 时为样例

当 $N=5$ 时,可以用两个2的子树拼成

然后我们发现,能作为右子树的只有 $2/4$ ,前五个都不是满二叉树,所以我们可以合并两颗树,当且仅当两个二叉树高度相同

发现2的高度为2,没有与之相同树高的树,所以能作为右子树的只有 $4$

所以我们就有:用 $4/5$ 可以凑出 $9/10$ , $9/10$ 又可以拼出 $19/20$ ……

所以我们就可以用 $4/5$ 一路递推下去,发现每次都*了 $2$ ,所以复杂度为 $O(logN)$

$Code:$

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n, x = 4, y = 5;
    scanf("%d", &n);
    if(n == 1 || n == 2) return puts("1"), 0;
    while(y < n) {
        if(x & 1) x = 2 * y, y = x + 1;
        else x = 2 * y - 1, y = x + 1;
    }
    return printf("%d", (x == n || y == n)), 0;
}