大家好,欢迎来到IT知识分享网。
[SHOI2012]随机树
有一个二叉树,生成方式如下,初始只有一个根节点,所有的树的状态接下来按照,随机选择一个叶节点,加上其左右儿子,现在有两个询问
- 有n个叶结点的树的叶结点的平均深度的期望。
- 有n个叶结点的树的深度的期望,定义根节点深度为0
\(n\leq 100\)
解
询问1:
注意到平均深度的期望,换种解释即叶结点深度的期望,于是根据此,我们设\(f[i]\)表示有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]不好求,于是猜测为条件概率问题,设i,j以前概率\(p[i][j]=\frac{1}{i-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的概率,不难由容斥原理有
\(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