题面
https://www.luogu.org/problemnew/show/P3830
题解
第一问:
设 \(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<bits/stdc++.h>
- #define LL long long
- #define RG register
- using namespace std;
- template<class T> 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<class T> 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;
- }
来源: http://www.bubuko.com/infodetail-2991409.html