网站建设山东聚搜网络y,微信小商城怎么开通,建个人博客网站,企业网站剖析传送门#xff1a;洛谷 题目大意#xff1a;对于一个只有一个节点的二叉树#xff0c;一次操作随机将这棵树的叶节点的下方增加两个节点。$n-1$次操作后变为$n$个叶节点的二叉树。求#xff1a;#xff08;1#xff09;叶节点平均深度的期望值#xff08;2#xff09;树… 传送门洛谷 题目大意对于一个只有一个节点的二叉树一次操作随机将这棵树的叶节点的下方增加两个节点。$n-1$次操作后变为$n$个叶节点的二叉树。求1叶节点平均深度的期望值2树深度的数学期望值 数据范围$2\leq n\leq 100$ 首先看第1问 设$f_i$为$i$个叶节点的二叉树的叶节点平均深度的期望值。 每次选择一个叶节点扩展出两个新的叶节点所以总的深度增加$f_{i-1}2$ 则$f_i\frac{(i-1)*f_{i-1}f_{i-1}2}{i}f_{i-1}\frac{2}{i}$ 所以 $$Ans\sum_{i2}^n\frac{2}{i}$$ 然后是第2问这个难度要稍微大一点。 我们发现这求的是$n$个数的最大值的期望而第1问的是和的期望而期望可加却不能$\max$就非常不好办了。 这时我们就需要用一个式子 $$E[X]\sum_{i1}^{n-1}P(X\geq i)$$ 然后就可以转化为其中一个数$\geq i$的概率。 就很容易想到$dp[i][j]$表示$i$个叶节点的二叉树中深度$\geq j$则左子树深度$\geq j-1$或右子树深度$\geq j-1$ 所以 $$dp[i][j]\frac{\sum_{k1}^{i-1}(dp[k][j-1]dp[i-k][j-1]-dp[k][j-1]*dp[i-k][j-1])}{i-1}$$ $$Ans\sum_{i1}^{n-1}dp[n][i]$$ 然后就做完了。 1 #includecstdio2 #define Rint register int3 using namespace std;4 const int N 103;5 int q, n;6 double dp[N][N], ans;7 int main(){8 scanf(%d%d, q, n);9 if(q 1)
10 for(Rint i 2;i n;i ) ans 2.0 / i;
11 else {
12 for(Rint i 1;i n;i ) dp[i][0] 1;
13 for(Rint i 2;i n;i ){
14 for(Rint j 1;j n;j ){
15 for(Rint k 1;k i;k )
16 dp[i][j] dp[k][j - 1] dp[i - k][j - 1] - dp[k][j - 1] * dp[i - k][j - 1];
17 dp[i][j] / i - 1;
18 }
19 }
20 for(Rint i 1;i n;i ) ans dp[n][i];
21 }
22 printf(%.6f, ans);
23 } Luogu3830 转载于:https://www.cnblogs.com/AThousandMoons/p/10595583.html
