Codeforces 1237E. Balanced Binary Search Trees

传送门

这一题是真的坑人，时间空间都在鼓励你用 $NTT$ 优化 $dp$...（但是我并不会 $NTT$）

看到题目然后考虑树形 $dp$ ，设 $f[i][0/1]$ 表示 $i$ 个节点的树，根节点为奇数/偶数的方案数

然后发现对于 $f[i][0/1]$ 的所有方案，把节点编号同时加一个偶数后根节点奇偶性不变，把节点编号加一个奇数后根节点的奇偶性变了

那么就可以对每个 $f[i][0/1]$ 枚举左右子树转移了，因为确定总点数所以左子树点数就有一个范围，在那个范围内枚举子树大小 $j$

那么有转移 $f[i][0]=\sum f[j][1] \cdot f[i-j-1][1]$ ，$f[i][1]=\sum f[j][0] \cdot f[i-j-1][1]$

然后发现转移是卷积的形式，然后据说就可以 $NTT$ 优化什么的...但是我完全不会诶

然后推完发现并没有什么用就去看看神仙的提交记录（比赛的时候是可以看别人的提交结果的）

然后你感到一丝不妙，那些人怎么都是几十毫秒过的？？？再看看空间发现有些人甚至 $0kb$ ？？？

于是你赶紧把暴力打完把表打出来，发现大部分状态都是 $0$ ，只有少部分的结果是 $1$

然后你再输出一下方案为 $1$ 的各种状态，发现只有当节点数为 $1,2,4,5,9,10,20,21,41,42,84,85...$

然后就发现了规律，然后你就成功通过了这一题（当然那时我并没有过）

所以现在考虑一下怎么去证明这个东西，首先对于 $3$ 层的这种树只有当点数为 $4,5$ 时可以发现有唯一一种方案

首先显然的，对于这种树的根节点，它的左右儿子子树也必须是这种树

然后注意到对于 $n$ 个节点的这种树，根节点和 $n$ 号节点奇偶性相同（因为二叉搜索树的性质，$n$ 号节点必须是最右边的）

所以根节点的右子树的子树大小必定为偶数

然后又因为左右子树的深度必须一样，所以比 $4,5$ 个节点的这种树多一层的这种树，它的左右儿子必须是 $4$ 或 $5$ 个节点

又因为之前证明的右儿子必须为偶数，那么多一层的这种树只有左儿子为 $4$ 右儿子为 $4$ ，和左儿子为 $5$ 右儿子为 $4$ 两种方案

那么每一层都只能靠少一层的那两种子树得到新的那两种树，所以证明完毕

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=1e6+;

int n;

int main()

{

    n=read();

    int now=;

    while(now<=n)

    {

        if(now==n || now+==n) { printf("1\n"); return ; }

        if(now&) now=(now+)++now;

        else now=now++now;

    }

    printf("0\n");

    return ;

}

巴特西

Codeforces 1237E. Balanced Binary Search Trees

最新文章

热门文章