【概率与期望专题】

一些概念

样本空间S:一个集合

基本事件a:$a \in S$

事件A:$A \subseteq S$

A与B的并:$A \cup B$

A与B的交:$A \cap B$

A与B互斥:$A \cap B= \varnothing$

B关于A的条件概率:$P(B|A)= \frac{P(A \cap B)}{P(A)}$

A,B独立:$P(A \cap B)=P(A)P(B) \Rightarrow A \bot B$

数学期望:随机变量在概率加权下的平均值

$$ E(X)=\sum_{i=1}^n X_i P_i $$

期望的线性性:

$$\forall X,Y \Rightarrow E(aX+bY)=aE(X)+bE(Y)$$



T1

给出一棵n个节点的树,每次随机选择一个未染色的节点将其与其子树上全部节点染色,问整棵树全部染色的期望操作次数。

对于节点x,只有其祖先节点对其贡献有影响。

考虑到选了祖先就不会选该节点,故选该节点的概率为$\frac{1}{dep[x]}$

选该节点的期望也就是$\frac{1}{dep[x]} \cdot 1=\frac{1}{dep[x]}$

由期望的线性性,整棵树的期望操作次数就是每个节点的操作次数之和

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN=1e5+5;

int n,np;
int dep[MAXN],h[MAXN];
struct rpg{
    int li,nx;
}a[MAXN<<1];

void add(int ls,int nx)
{
    a[++np]=(rpg){h[ls],nx};
    h[ls]=np;
}

void dfs(int x,int f)
{
    dep[x]=dep[f]+1;
    for(int i=h[x];i;i=a[i].li)
        if(a[i].nx!=f) dfs(a[i].nx,x);
    return;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }dfs(1,0);double ans=0;
    for(int i=1;i<=n;++i) ans+=1.0/dep[i];
    printf("%.18lf\n",ans);
    return 0;
}

T2

给出一个有向无环图,从起点出发,对于每个节点都等概率地选择一条边离开该点,问从起点到终点的路径总长度期望是多少。

有向无环图上跑拓扑排序即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN=1e5+5;

int n,m,np;
int h[MAXN],q[MAXN],odeg[MAXN],ideg[MAXN];
double Ep[MAXN],Ek[MAXN];
struct rpg{
    int li,nx,ln;
}a[MAXN<<1];

void add(int ls,int nx,int ln)
{
    a[++np]=(rpg){h[ls],nx,ln};
    ++odeg[ls];++ideg[nx];h[ls]=np;
}

void tps()
{
    int hd=1,tl=1;
    q[hd]=1;Ep[1]=1;
    while(hd<=tl){
        int nw=q[hd++];
        for(int i=h[nw];i;i=a[i].li){
            double pw=1.0/odeg[nw];
            Ep[a[i].nx]+=pw*Ep[nw];
            Ek[a[i].nx]+=pw*Ek[nw]+pw*Ep[nw]*a[i].ln;
            --ideg[a[i].nx];
            if(!ideg[a[i].nx]) q[++tl]=a[i].nx;
        }
    }return;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }tps();
    printf("%.2lf",Ek[n]);
    return 0;
}

T3

[HNOI2013]游走

题目链接

像上面那样列式,高斯消元即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN=505;

int n,m;
int deg[MAXN];
double ct[MAXN][MAXN];
bool mtrx[MAXN][MAXN];
struct rpg{
    int x,y;
    double E;
}line[MAXN*MAXN];

inline bool kpz(double x){return -1e-8<x&&x<1e-8;}

void Gauss()
{
    for(int i=1;i<n;++i){
        double pw=1/ct[i][i];
        for(int j=i;j<=n+1;++j) ct[i][j]*=pw;
        for(int j=i+1;j<=n;++j){
            double pw=ct[j][i]/ct[i][i];
            for(int k=i;k<=n+1;++k) ct[j][k]-=ct[i][k]*pw;
        }
    }for(int i=n;i;--i){
        for(int j=i-1;j;--j){
            double pw=ct[j][i]/ct[i][i];
            ct[j][i]=0;ct[j][n+1]-=ct[i][n+1]*pw;
        }
    }return;
}

bool cmp(rpg a,rpg b){return a.E>b.E;}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        ++deg[x];++deg[y];
        mtrx[x][y]=mtrx[y][x]=1;
        line[i]=(rpg){x,y};
    }
    for(int i=1;i<n;++i){
        ct[i][i]=1;
        for(int j=i+1;j<n;++j)
            if(mtrx[i][j]){
                ct[i][j]=-1.0/deg[j];
                ct[j][i]=-1.0/deg[i];
            }
    }ct[1][n+1]=ct[n][n]=ct[n][n+1]=1;
    Gauss();
    for(int i=1;i<=m;++i){
        int x=line[i].x,y=line[i].y;
        if(x!=n) line[i].E+=ct[x][n+1]/deg[x];
        if(y!=n) line[i].E+=ct[y][n+1]/deg[y];
    }sort(line+1,line+m+1,cmp);
    double ans=0;
    for(int i=1;i<=m;++i) ans+=line[i].E*i;
    printf("%.3lf\n",ans);
    return 0;
}