SHOI 2012 D1-T3 随机树

~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

[SHOI2012] 随机树

题面

---

Input

输入仅有一行，包含两个正整数 $q, n​$，分别表示问题编号以及叶结点的个数。

---

Output

输出仅有一行，包含一个实数 $d​$，四舍五入精确到小数点后 $6​$ 位。如果 $q = 1​$，则 $d​$ 表示叶结点平均深度的数学期望值；如果 $q = 2​$，则 $d​$ 表示树深度的数学期望值。

---

Sample Input/Output

Sample Input 1	Sample Output 1
1 4	2.166667
Sample Input 2	Sample Output 2
2 4	2.666667
Sample Input 3	Sample Output 3
1 12	4.206421
Sample Input 4	Sample Output 4
2 12	5.916614

---

Hint

#1,2:$q=1,2\le n\le 10$

#3,4,5:$q=1,2\le n\le 100$

#6,7:$q=2,2\le n\le 10$

#8,9,10:$q=2,2\le n\le 100​$

---

对于第1问：

要求平均叶子节点的深度的期望，用$dp$写。

有个很显然的$dp$方程，设$f[i]$代表有$i$个叶子节点时树的平均深度，每展开一次就会多出来一个叶子节点，所以状态直接由$f[i-1]→f[i]$，有一个比较显然的方程$f[i]=f[i-1]+\frac 2i$。

怎么说呢，比较显然的规律：

假设我们当前已经生成了$i-1​$的节点，因为这是一棵二叉树，所以我们第$i​$个节点只有$i​$个地方可以生成（不信的话你们可以自己xjb画一棵树试试）。我们只有在深度最深的那个节点处加左/右儿子的话才能够使$i​$个节点的树平均深度增加，即我们有$\frac 2i​$的概率能使$i-1​$个节点的树$+1​$深度，就能得到上一方程。

（好像有点问题，下面好像比较对，2019.3.13留）

由于我们要求平均值，若我们当我们要生成$i​$个叶节点时，设当前要展开一个叶子节点$x​$，原$i-1​$个叶子节点深度和为$f[i-1]×(i-1)​$，我们可以所有已有的叶节点的深度看成是平均深度（本题的精髓），即我们新展开出来的叶节点$i​$的父亲$x​$深度为$f[i-1]​$，$i​$的深度是$f[i-1]+1​$，那么我们要使原叶子节点$x​$同时有左右儿子，并且我们此时的$x​$节点已经不是叶子节点了，所以有$dp​$方程：

$$f[i]=\frac {f[i-1]×(i-1)+(f[i-1]+1)×2-f[i-1]}{i}=\frac {f[i-1]*i+2}{i}=f[i-1]+\frac 2i​$$

初始状态$f[1]​$=0。

答案为$ans=f[n]​$。

对于第2问：

在做这一问前，我们先来看个公式：

• 令任意一个变量$k​$的期望为$E(x)​$。
• 那么$E(x)=\sum_{i=1}^{+∞}P_iW_i$。
• 展开一次的贡献只能是$1$，此时有$W_i=1(i∈N^*)$
• 这样我们就将题目中所要求的的期望转化成了求概率。
• 那么我们所要求的$E(x)=\sum_{i=1}^{+∞}P_i​$

对于第二问，设我们当前这棵树有$i$个叶子节点，深度$≥j$，出现这样的状态的概率为$f[i][j]$。

我们是否要$for(int\ i=1;;++i)​$呢？

显然是不用的：

∵i>=n时是没有意义的，不存在这样的情况，所以我们将上述公式里的+∞缩减为$n-1​$就足够了

∴我们要求的答案：$ans=\sum_{i=1}^{n-1}f[n][i]$

我们逐个枚举；因为我们枚举左右子树各有多少叶子节点时，令一边的子树内有$num$个点，由于我们展开一个节点，必定都有左右子树，所以子树大小$num$至少为1，两边的深度都$≥j-1$（此时自动去掉计算根节点，去调用左右子树$f[num][j-1]$和$f[i-num][j-1]$的概率）的情况会计算两次，直接套用一下容斥原理，减掉一次。

转移方程为：$f[i][j]=\sum_{num=1}^{i-1}\frac{f[num][j-1]+f[i-num][j-1]-f[num][j-1]×f[i-num][j-1]}{i-1}​$

---

Code

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x = 0, w = 0;
	char ch = 0;
	while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return w ? -x : x;
}
double f1[110], f2[110][110], ans;
int main(int argc, char const *argv[])
{
	int q = read(), n = read();
	if (q == 1)
	{
		f1[1] = 0.0;
		for (int i = 2; i <= n; ++i) f1[i] = f1[i - 1] + 2.0 / i;
		printf("%.6lf", f1[n]);
	}
	else
	{
		for (int i = 1; i <= n; ++i) f2[i][0] = 1;
		for (int i = 2; i <= n; ++i)
		{
			for (int j = 1; j < i; ++j)
			{
				for (int num = 1; num < i; ++num)
					f2[i][j] += f2[num][j - 1] + f2[i - num][j - 1] - f2[num][j - 1] * f2[i - num][j - 1];
				f2[i][j] = f2[i][j] / (i - 1);
			}
		}
		for (int i = 1; i < n; ++i) ans += f2[n][i];
		printf("%.6lf", ans);
	}
	return 0;
}