[SHOI2012]随机树

[SHOI2012]随机树"[SHOI2012]随机树"有一个二叉树,生成方式如下,初始只有一个根节点,所有的树的状态接下来按照,随机选择一个叶节点,加上其左右儿子,现在有两个询问1.有n个叶结点的树的叶结点的平均深度的期望。1.有n个叶结点的树的深度的期望,定义根节点深度为0$n\leq1

大家好,欢迎来到IT知识分享网。[SHOI2012]随机树"

[SHOI2012]随机树

有一个二叉树,生成方式如下,初始只有一个根节点,所有的树的状态接下来按照,随机选择一个叶节点,加上其左右儿子,现在有两个询问

  1. 有n个叶结点的树的叶结点的平均深度的期望。
  2. 有n个叶结点的树的深度的期望,定义根节点深度为0

\(n\leq 100\)

询问1:

注意到平均深度的期望,换种解释即叶结点深度的期望,于是根据此,我们设\(f[i]\)表示有i个叶结点的树的叶结点深度期望,所以不难有

\[f[i]=\frac{f[i-1]\times(i-1)+f[i-1]+2}{i} \]

含义即f[i-1]先乘i-1变为i-1个叶结点树的叶结点深度和期望加上i-1个叶结点深度的期望处以叶结点个数,其实没有加两倍f[i-1],原因在于分子左式以及算过一次了。

询问2:

  • 思路一

显然想设\(f[i]\)表示有i个叶结点的树的深度期望,于是发现此时不知道在哪里加会使深度增加,于是我们的表现出深度这个状态,于是设\(f[i][j]\)表示有i个叶结点深度为j的概率,因为已经表现出了深度,无需把方程设成期望,概率更好做,转移根据二叉树根节点左右子树划分,设\(p[i][l]\)为有i个叶子结点的树左子树有j个叶子节点的概率,于是不难有

\[p[i][j](f[j][l]+f[i-j][r])=f[i][max(l,r)+1] \]

而显然p[i][j]不好求,于是猜测为条件概率问题,设i,j以前概率\(p[i][j]=\frac{1}{i-1}\),于是对于

\[p[i+1][j]=p[i][j]\frac{i-j}{i}+p[i][j-1]\frac{j-1}{i} \]

\[=\frac{1}{i-1}\frac{i-j}{i}+\frac{1}{i-1}\frac{j-1}{i} \]

\[=\frac{1}{i} \]

于是原方程为

\[\frac{1}{i-1}(f[j][l]+f[i-j][r])=f[i][max(l,r)+1] \]

以此\(O(n^4)\)转移即可。

参考代码:

#include <iostream>
#include <cstdio>
#define il inline
#define ri register
using namespace std;
double f1[101],f2[101][101];
template<class free>
il free Max(free,free);
int main(){
    int q,n,i,j,l,r;
    scanf("%d%d",&q,&n);
    if(q==1){
        for(i=2;i<=n;++i)f1[i]=f1[i-1]+2.0/i;
        printf("%.6lf",f1[n]);
    }
    else{
        double ans(0);f2[1][0]=1;
        for(i=2;i<=n;++i)
            for(j=1;j<=i;++j)
                for(l=0;l<=n;++l)
                    for(r=0;r<=n;++r)
                        f2[i][Max(l,r)+1]+=f2[j][l]*f2[i-j][r]/(i-1);
        for(i=0;i<=n;++i)ans+=f2[n][i]*i;printf("%.6lf",ans);
    }
    return 0;
}
template<class free>
il free Max(free a,free b){
    return a>b?a:b;
}

  • 思路二

如果忘记二叉树递推左右子树划分的套路,可以根据不好递推状态,采取拆分的方式设状态,于是设\(f[i][j]\)表示有i个叶子节点,深度大于等于j的概率,不难由容斥原理有

\[f[i][j]=\frac{f[k][j-1]+f[i-k][j-1]-f[k][j-1]\times f[i-k][j-1]}{i-1} \]

\(O(n^3)\),比思路一优秀得多,不难得出结论,拆分是优化递推的有力工具。

参考代码:

#include <iostream>
#include <cstdio>
#define il inline
#define ri register
using namespace std;
double f1[101],f2[101][101];
int main(){
    int q,n,i,j,k;
    scanf("%d%d",&q,&n);
    if(q==1){
        for(i=2;i<=n;++i)f1[i]=f1[i-1]+2.0/i;
        printf("%.6lf",f1[n]);
    }
    else{
        f2[1][0]=1;double ans(0);
        for(i=2;i<=n;++i)
            for(f2[i][0]=1,j=1;j<=n;f2[i][j]/=(i-1),++j)
                for(k=1;k<i;++k)
                    f2[i][j]+=f2[k][j-1]+f2[i-k][j-1]-f2[k][j-1]*f2[i-k][j-1];
        for(i=1;i<=n;++i)ans+=f2[n][i];
        printf("%.6lf",ans);
    }
    return 0;
}

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/30667.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信