题面

题解

第一问:

设\(f[i]\)表示\(i\)步操作后,平均深度期望

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

第二问就比较难受了:

\(E(x)=∑_{i=1}^{x}P\)

随机变量\(x\)的期望为对于所有\(i\)，\(i≤x\)的概率之和

我们设\(f[i][j]\)表示\(i\)步后,树的深度\(>=j\)的概率

我们每次新建一个根,然后枚举左右子树分配节点情况

\(f[i][j] = \frac{1}{i-1}\sum_{k=1}^{i-1}(f[k][j-1]*1+f[i-k][j-1]*1-f[k][j-1]*f[i-k][j-1])\)

然后

\(Ans = \sum_{i=1}^{n-1}f[n][i]\)

Code

#include
    
     #define LL long long#define RG registerusing namespace std;template
     
       inline void read(T &x) {    x = 0; RG char c = getchar(); bool f = 0;    while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;    while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();    x = f ? -x : x;    return ;}template
      
        inline void write(T x) {    if (!x) {putchar(48);return ;}    if (x < 0) x = -x, putchar('-');    int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;    for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;}const int N = 110;int q, n;namespace cpp1 {    double f[N];    void main() {        for (int i = 2; i <= n; i++) f[i] = f[i - 1] + 2.0 / i;        printf("%lf\n", f[n]);        return ;    }}namespace cpp2 {    double f[N][N];    void main() {        for (int i = 1; i <= n; i++) f[i][0] = 1;        for (int i = 2; i <= n; i++)            for (int j = 1; j < n; j++) {                for (int k = 1; k < i; k++)                    f[i][j] += f[k][j - 1] + f[i - k][j - 1] - f[k][j - 1] * f[i - k][j - 1];                f[i][j] /= (i - 1);            }        double ans = 0;        for (int i = 1; i < n; i++) ans += f[n][i];        printf("%lf\n", ans);    }   }int main() {    read(q), read(n);    if (q == 1) cpp1 :: main();    else cpp2 :: main();    return 0;}