「有趣的(纯)找性质题」[Global Round #5] Balanced Binary Search Trees

皎月半洒花 · 2020-06-05 07:30:38 · 题解

发现这个 balanced 是个很强的约束，可以观察到在第一个条件下根节点只能是 \left\lceil\dfrac{n}{2} \right\rceil 或者 \left\lfloor\dfrac{n}{2} \right\rfloor 。然后紧接着可以发现每个子树在第一个约束下都只能是类似状态。然后考虑第二个条件，一个很重要的事实在于，可以发现键值 n 永远是在最右侧的链，所以可以知道 n 一定和 root 的键值奇偶性相同。接着，由于右子树的点集是 [root,n] ，那么不难知道每个根的右子树 size 都必然是偶数 。

有了这些性质，可以发现对于每个 n ，答案至多为 1 。

证明可以考虑假设有两个均满足条件的树 T_1,T_2 ，那么他们一定有某部分同构，剩下的部分不同构。考虑不同构的那部分，由于要满足 perfect balanced ，所以可以知道「不同构」只能是把某个点的某个子树的一个点移到另一颗子树里，这要满足两个子树 size 之前相差 1 ，所以 T_1,T_2 中必然有一棵树满足存在一个点，其右子树的 size 是奇数。所以可知答案至多为 1 。

于是就可以直接从 size=1 开始构造了。复杂度 \log n 。

#include <cstdio>

int n ;
int ans ;

int main(){
    ans = 1 ;
    scanf("%d", &n) ;
    while (ans <= n){
        if (ans == n || ans == n - 1) return puts("1"), 0 ;
        if (ans & 1) (ans <<= 1) += 2 ; else (ans <<= 1) += 1 ;
    }
    return puts("0"), 0 ;
}