This page looks best with JavaScript enabled

「SHOI2012」随机树-期望dp

 ·  ✏️ About  493 words  ·  ☕ 1 mins read · 👀6 views

题面以图片显示,请点击“阅读全文”查看。

链接🔗

Luogu P3830

题解🔗

这题有两问。

第一问🔗

如果令 dp[x] 为有 x 个叶节点的时候叶节点的平均深度,那么有如下方程:
dp[x]=(x1)dp[x1]dp[x1]+2×(dp[x1]+1)x =dp[x1]+2x

初始 dp[1]=0O(n) 递推或者搞一搞通项即可qwq。

第二问🔗

树的深度不太好搞。

定理:
E(x)=i=1+P(ix)

感性理解:大小为 x 的可能性就会被从 i=1i=x 一直累积,累积正好就是 x 次,就是这种可能性的值,所以这个式子的值就是期望。

所以我们只要求出在树的叶节点有 x 个的时候,求出树的深度 i 大于 1 ,大于 2 ,…,一直到大于 n1 的概率,然后求和之后就是树的期望深度了。

dp[x][j] 为有 x 个叶节点时树的深度大于 j 的概率,因为展开在两侧时完全等概率的,所以我们有如下方程:

dp[x][j]=1x1(i=1x1dp[i][j1]+dp[xi][j1]dp[i][j1]×dp[xi][j1])

很简单的容斥。转移即可。注意一下边界,和根结点深度为0即可。

代码🔗

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
using namespace std;

const int MAXN = 200;

double cal(int n,int op){
    double ans = 0;
    if(op == 1)
        for(int i = 2;i<=n;i++) ans += (2/double(i));
    else {
        static double d[MAXN][MAXN];
        for(int i = 1;i<=n;i++)
            d[i][0] = 1;
        for(int i = 2;i<=n;i++){
            for(int j = 1;j<i;j++){
                for(int k = 1;k<=i-1;k++)
                    d[i][j] += d[k][j-1] + d[i-k][j-1]- d[k][j-1] * d[i-k][j-1];
                d[i][j] /= (i-1); 
            }
        }
        for(int i = 1;i<=n-1;i++)//从1开始枚举
            ans += d[n][i];
    }
    return ans;
}

int main(){
    int q,n;
    scanf("%d %d",&q,&n);
    printf("%lf\n",cal(n,q));
    return 0;
}

cqqqwq
WRITTEN BY
cqqqwq
A student in Software Engineering.


Comments