题解：CF1237E Balanced Binary Search Trees

· · 题解

对 https://www.luogu.com.cn/article/fd9qi7ie 的一些补充。

step1：容易发现根的奇偶性和 n 的奇偶性相同。所以根的右子树大小一定是偶数。

step2：一颗合法的树，满足根的左右子树也是合法的树。

step3：2^k - 1 显然是奇数，所以一颗满二叉树（除了只有一个点的树）一定是不合法的。

step4：一个合法的树，根的左右子树也都是合法的树。

考虑两个合法的树合并为一个合法的树。

题目中要求每个点到根的距离的和最小，也就是树是一颗满二叉树在最后一层删除一些点得到。所以那两个合法的树必须高度相同为 i（如果不同，第一种情况是其中一棵树是满二叉树，这不合法，第二种情况反之，这样合并出来的树不合法）。

设 f_i 表示深度为 i 的合法的树的最小大小。对于 i \le 2 先特判掉。

接下来需要证明深度为 i(i \ge 3) 的合法的数的大小值有且只有可能 f_i 或 f_i+1。考虑归纳法证明：

顺便也得出了转移式 f_i = 2 \times f_{i-1} + 1 + [f_{i-1} \bmod 2 = 1]。

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

int n, f[30];

int main(){
    cin >> n;
    if(n == 1 || n == 2 || n == 4 || n == 5){
        cout << 1;
        return 0;
    }else if(n == 3){
        cout << 0;
        return 0;
    }
    f[3] = 4;
    for(int i = 4; i <= 25; i++){
        f[i] = 2 * f[i - 1] + 1 + (f[i - 1] % 2 == 1);
        if(f[i] == n || f[i] + 1 == n){
            cout << 1;
            return 0;
        }
    }
    cout << 0;
    return 0;
}