BZOJ 3057圣主的考验题解

老师居然考这么毒瘤的题目！！！！！

很容易想到dp，f[i][j]表示有i个节点，左子树的最深深度为j的方案数

枚举左子树有多少节点然后转移，复杂度为n^3

T飞~

我们考虑到有深度为h的树的节点有多少，可以发现深度为h的节点有着一定的范围

设minn为深度为h的树最少有多少节点，maxh为深度为h的数最多有多少节点

很显然minn[h]=minn[h-1]+minn[h-2]+1,maxh[h]=2^h-1

我们每一次转移时依然枚举左子树节点个数i，再次枚举深度是只需要枚举所有minn[h]<=i，切maxh[h]>=h的深度h

这样复杂度就变成了n^2*h，h为maxh[h]>3000的第一个h大约为20

但是它神奇的T掉了，我也不知道为什么......

# include<cstdio>

# include<cstring>

# include<cstdlib>

# include<algorithm>

using namespace std;

typedef long long LL;

const int mn = ;

const int mod = ;

int maxh[],minh[],L[mn + ],R[mn + ];

LL dp[mn + ][],ans[mn + ];

int main ()

{

    dp[][]=dp[][]=, ans[]=;

    minh[]=,minh[]=;

    for(int i=;i<=;i++)

        minh[i]=minh[i-]+minh[i-]+;

    for(int i=;minh[i]<=mn && i<= ;i++)

        for(int j=minh[i];j<min(minh[i+],mn+);j++)

            R[j]=i;

    maxh[]=;

    for(int i=;i<=;i++)

      maxh[i]=maxh[i-]*+;

     L[]=;

     for(int i=;maxh[i-]<=mn && i<=;i++)

        for(int j=maxh[i-]+;j<=min(maxh[i],mn);j++)

            L[j]=i;

     for(int i=;i<=mn;i++)

     {

        for(int l=;l<i;l++)

        {

            int r=i--l;

            for (int h=max(,L[i]-);h<=min(,R[i]-);h++)

            {

                if(h)

                dp[i][h+]+=dp[l][h]*dp[r][h-];

                (dp[i][h+]+=dp[l][h]*dp[r][h])%=mod;

                dp[i][h+]+=dp[l][h]*dp[r][h+];

            }

        }

        for(int h=;h<=min(,i);h++)

            ans[i]+=dp[i][h];

        ans[i] %= mod;

    }

    int n;

    while(scanf("%d",&n),n)

       printf(n>= ? "%09lld\n" : "%lld\n",ans[n]);

    return ;

}

巴特西

BZOJ 3057圣主的考验题解

最新文章

热门文章