CF1237E Balanced Binary Search Trees

神在哪里。

首先这意味着只有最后一层是不满的，可以散着一些叶子。否则你可以把最深的叶子往上提一层。

然后根据 BST 一个节点对应一个区间的规则，不难想到一个区间 DP。 表示值域在 之间，根节点奇偶性是偶数/奇数的情况。转移是枚举一下最后一层分给左侧几个叶子，右侧几个叶子，算出根节点，然后根据根节点奇偶性做转移。

然后有一个观察，就是你发现给值域整体加上一个 是不会破坏奇偶性要求的。因此后文编号一律从 开始。根据这个我们发现你只需要记录子树大小即可，对根节点的奇偶性做对应变化。

分讨一下根节点奇偶性：

• 根节点编号 ，对于右子树，我们需要加上 ，并且加完之后要模 同余 ，不妨将右子树根节点设为 ，那么有 ，根据 简单推一下发现 。左子树显然根节点是奇数。
• 根节点编号 ，对于右子树有 ，推一下还是可以得到 ，左子树根节点是偶数。

因此右子树一定从 转移过来，左子树则要看根节点奇偶性。编辑情况 。

优化转移的最简单做法就是打张表。只需要花 秒钟就能看出来规律了。

我们继续观察。手玩一下小的情况，发现 无解（样例给了）， 答案是 （样例给了）并且根是奇数。 你手玩一下发现答案也是 且根是偶数。

那么我们不难发现，有解的情况是比较稀疏的，并且答案比较小。

我们尝试通过已经有的情况拼凑出下一个可行的大小。 和 显然是不能组合在一起的，因为层数不一样。 已经算完了，得到了 。因为右子树一定是奇数根，因此右子树大小一定是 ，对于左子树是 的情况可以分别得到 的一个解。然后你发现 和 的层数也不一样。此时我们继续用 去推，可以得到 的解。

我们简单整理一下发现，假设连续两个有解的答案是 ，那么下一个答案是

• ，对于 是奇数根的情况。
• ，对于 是奇数根的情况。

并且不难发现， 一定同层，且 和 一定不能组合。这是因为 和 的最后一层都不是满的（因为叶子永远是从上一个继承过来的，实际上对于所有满二叉树都无解，因为满二叉树的划分方式是唯一的，划分到 的时候就无解了），并且 相较于 增加了一层。

或者可以从另一个角度考虑。转移要么是 ，要么是 ，要么是 ，可以证明在原先不是 的前提下，这些转移都不会转移到 。

那么，花 的时间预处理，查询的时候查表即可。

此外还有另外一个比较巧妙的做法。就是考察 dfn 序永远是一奇一偶，照着这个贪心构造出一棵树看看能否构造出来即可。细节可以看别人的题解。这里不再赘述。

▶

INFO

#include <array>
#include <iostream>

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
 
namespace solve {
const uint N = 1e6 + 5;
std::array<uint, N> ans{0, 1, 1};
 
void prework() {
    uint a = 4, b = 5;
 
    bool x = false;
 
    while (a < N || b < N) {
        if (a < N) {
            ans[a] = 1;
        }
        if (b < N) {
            ans[b] = 1;
        }
        if (!x) {
            a *= 2;
            ++a;
            b = a + 1;
        }
        else {
            a = b * 2;
            b = a + 1;
        }
        x = !x;
    }
}
 
void solve() {
    uint n;
    std::cin >> n;
 
    std::cout << ans[n] << "\n";
}

} // namespace solve

int main() {
    solve::prework();
   solve::solve();
   std::cout << std::flush;
}