笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

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

posted on 2020-06-05 07:30:38 | under 题解 |

发现这个 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 ;
}