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

发现这个 `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$ 。 ```cpp #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 ; } ```