「shoi 2012」随机树

link.

对于 pass 1, 你把他考虑成 $\frac{\sum x}{i}$ 的形式, 于是每次操作的贡献就是 $\frac{2}{i}$, 那么答案就是 $\sum_{i=2}^n\frac{2}{i}$.

对于 pass 2, 首先由全概率公式 $\textbf{E}(n)=\sum_{i=0}^{\infty}\textbf{P}(n\geqslant i)$. 那么我们考虑固定 $k=i$, 求出 $\textbf P(n\geqslant k)$. 其实直接求这个有点麻烦, 强化一下条件, 我们求 $\textbf P(n=k)$, 最后后缀和即可取得 $\textbf P(n\geqslant k)$.

设 $f(i,j)$ 表示共 $i$ 个叶结点, 树深度为 $j$ 时的概率. 对于二叉树我们有一种经典的考虑子结构的方式, 即考虑左子树的信息. 对于此题, 我们考虑左子树 (相对于根结点来说) 的叶结点数量 $k$. 那么有 $f(i,\max\{k,l\}+1)\gets f(i,\max\{k,l\}+1)+\frac{f(j,k)\times f(i-j,l)}{i-1}$. 其中 $i$ 为全树的叶子个数, $k$, $l$ 分别为左, 右子树的深度, $j$ 为左子树的叶结点个数. $\frac{1}{i-1}$ 是对于一个有 $i$ 个叶子的二叉树, 有 $k$ 个结点在左子树的概率, which 与 $k$ 无关. 至于为什么是 $\frac{1}{i-1}$, 你考虑操作次数为 $i-1$ 即可.

#include <bits/stdc++.h>
using namespace std;
typedef double db;
int Q, N;
db f[200][200];
signed main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> Q >> N;
  cout << fixed;
  cout << setprecision(6);
  if (Q == 1) {
    db ans = 0;
    for (int i = 2; i <= N; ++i) {
      ans += 2.0 / i;
    }
    cout << ans << "\n";
  } else if (Q == 2) {
    f[1][0] = f[2][1] = f[3][2] = 1;
    for (int i = 4; i <= N; ++i) {
      for (int j = 1; j < i; ++j) {
        for (int k = 0; k < j; ++k) {
          for (int l = 0; l < i - j; ++l) {
            f[i][max(k, l) + 1] += f[j][k] * f[i - j][l] / (i - 1);
          }
        }
      }
    }
    db ans = 0;
    for (int i = N; i >= 1; --i) {
      f[N][i] += f[N][i + 1];
    }
    for (int i = 1; i < N; ++i) {
      ans += f[N][i];
    }
    cout << ans << "\n";
  }
  return 0;
}