概率期望

  1. 1 【bzoj 1076】[SCOI2008]奖励关
  2. 2 【cogs 1487】麻球繁衍
  3. 3 【cogs 1489】玩纸牌
  4. 4 【bzoj 1415】[Noi2005]聪聪和可可
  5. 5 【bzoj 3143】[Hnoi2013]游走

全概率公式: 全期望公式:

1 【bzoj 1076】[SCOI2008]奖励关

系统将依次随机抛出k次宝物,每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再吃)。 宝物一共有n种,系统每次抛出这n种宝物的概率都相同且相互独立。获取第i种宝物将得到Pi分,但并不是每种宝物都是可以随意获取的。第i种宝物有一个前提宝物集合Si。只有当Si中所有宝物都至少吃过一次,才能吃第i种宝物(如果系统抛出了一个目前不能吃的宝物,相当于白白的损失了一次机会)。假设你采取最优策略,平均情况你一共能在奖励关得到多少分值?

这是个状压dp
f[i][j]表示第i轮方案为j的期望值
据说要倒着推比较简单,统计答案就是f[1][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
#include<iostream>
#include<cstdio>
using namespace std;
int k,n,a[16],b[16];
double f[101][32768];
int main()
{
scanf("%d%d",&k,&n);
for(int i=1,x;i<=n;i++)
{
scanf("%d",&a[i]);
while(scanf("%d",&x)&&x) b[i]|=1<<(x-1);
}
for(int i=k;i;i--)
for(int t=0;t<(1<<n);t++)
{
for(int j=1;j<=n;j++)
if((b[j]|t)==t)
f[i][t]+=max(f[i+1][t],f[i+1][t|(1<<(j-1))]+a[j]);
else f[i][t]+=f[i+1][t];
f[i][t]/=n;
}
printf("%.6lf",f[1][0]);
}

2 【cogs 1487】麻球繁衍

有K个毛球。这种毛球只会存活一天。在死亡之前,一个毛球有Pi的概率生出i个毛球(i=0,1,...,n-1)。m天后所有毛球都死亡的概率是多少?(包含在第m天前全部死亡的情况)

由于每只麻球的后代独立存活,只需求出一开始只有1只麻球,m天后全部死亡的概率f(m)。
由全概率公式,有
其中Pjf(i1)jPj\cdot f(i-1)^j的含义是这个麻球生了j个后代,它们在i-1天后全部死亡。
由于一开始共有k只麻球,且各只麻球的死亡是独立的,由乘法原理,最终答案是f(m)kf(m)^k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int T,n,k,m;
double p[1000],f[1001];
int main()
{
scanf("%d",&T);
for(int cas=1;cas<=T;cas++)
{
scanf("%d%d%d",&n,&k,&m);
for(int i=0;i<n;i++) scanf("%lf",&p[i]);
memset(f,0,sizeof(f));
for(int i=1;i<=m;i++)
for(int j=0;j<n;j++)
f[i]+=p[j]*pow(f[i-1],j);
printf("Case #%d: %.6lf\n",cas,pow(f[m],k));
}
}

3 【cogs 1489】玩纸牌

玩纸牌,赢得概率为p,如果玩到实际获胜>p,开开心心睡觉去,直到玩了n次还没有成功,则以后再也不玩了。求玩的天数的期望值。

先研究一天“垂头丧气去睡觉”的概率Q
设f[i][j]表示前i局中每局结束后的获胜比例均不超过p,且前i局一共获胜j局的概率,则有:
f[i][j]=f[i-1][j]×(1-p)+f[i-1][j-1]×p (j/i<=p)
f[i][j]=0 (j/i>p)
则Q=f[n][0]+f[n][1]+...
则EX=Q+2Q(1-Q)+3Q(1-Q)^2+4Q(1-Q)^3+...
解得e=1/Q。(详见《训练指南》142页)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
using namespace std;
int a,b,n,T;
double p,ans,f[101][101];
int main()
{
scanf("%d",&T);
for(int cas=1;cas<=T;cas++)
{
f[0][0]=1;ans=0;
scanf("%d/%d%d",&a,&b,&n);
p=(double)a/b;
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++)
{
if(j*b<=a*i) f[i][j]=f[i-1][j]*(1-p)+(j?f[i-1][j-1]*p:0);
else f[i][j]=0;
}
for(int i=0;i*b<=a*n;i++) ans+=f[n][i];
printf("Case #%d: %d\n",cas,(int)(1.0/ans));
}
}

4 【bzoj 1415】[Noi2005]聪聪和可可

聪聪在C处,以后的每个时间单位,她会选一个更靠近可可的景点,如果这样的景点有多个,她会选一个标号最小的景点,并走两步。可可在K处,可可都会选择去相邻的景点(可能有多个)中的一个或停留在原景点不动,概率相等。在某一时刻,若聪聪和可可位于同一个景点,则可怜的可可就被吃掉了。求平均情况下,聪聪几步就可能吃到可可。

g[i][j]表示聪聪在i,可可在j时,聪聪会走到的点,即与i相邻的点中距离j最近且编号最小的点。
f[i][j]表示聪聪在i,可可在j时,聪聪抓住可可的平均步数。
设t=g[g[i][j]][j],则f[i][j]=f[t][to[j]]+f[t][j]du[i]+1+1f[i][j]=\frac{\sum f[t][to[j]]+f[t][j]}{du[i]+1}+1
其中f[i][i]=0;若g[g[i][j]][j]==j或g[i][j]==j,f[i][j]=1。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<cstring>
#include<cstdio>
#include<queue>
#define N 1001
using namespace std;
int n,m,S,T,ecnt=1,to[N*2],next[N*2],st[N],ds[N],du[N],g[N][N];
double f[N][N];
bool used[N];
queue<int> q;
void SPFA(int K)
{
memset(ds,0x7f,sizeof(ds));
memset(used,0,sizeof(used));
q.push(K);used[K]=1;ds[K]=0;g[K][K]=K;
while(!q.empty())
{
int x=q.front();q.pop();used[x]=0;
for(int i=st[x];i;i=next[i])
{
int y=to[i];
if(ds[y]>ds[x]+1)
{
ds[y]=ds[x]+1;
if(!used[y]) used[y]=1,q.push(y);
}
if(ds[y]<ds[g[x][K]]||(ds[y]==ds[g[x][K]]&&y<g[x][K])) g[x][K]=y;
}
}
}
double Search(int s,int t)
{
if(s==t) return 0;
if(g[s][t]==t||g[g[s][t]][t]==t) return 1;
if(f[s][t]) return f[s][t];
int C=g[g[s][t]][t];
double ans=Search(C,t);
for(int i=st[t];i;i=next[i]) ans+=Search(C,to[i]);
return f[s][t]=ans/(du[t]+1)+1;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&S,&T);
for(int i=1,x,y;i<=m;i++)
{
scanf("%d%d",&x,&y);
to[++ecnt]=y;next[ecnt]=st[x];st[x]=ecnt;du[x]++;
to[++ecnt]=x;next[ecnt]=st[y];st[y]=ecnt;du[y]++;
}
for(int i=1;i<=n;i++) SPFA(i);
printf("%.3lf",Search(S,T));
return 0;
}

5 【bzoj 3143】[Hnoi2013]游走

一个无向连通图,顶点从1编号到N,边从1编号到M。 小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和。
现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。

设p[i]为i点期望到达数次数.
这个对于1 < i <= n p[i]=sigma(p[j]/d[j]) (其中有边j,i)
特殊地,p[1]=1+sigma(p[j]/d[j]) (其中有边j,i)
而第N个点是终点,期望经过次数为0,不参与消元,因为走到N就停下了,不会经过
可得期望次数大的标号应该小
而p[e] = p[e.x] / du[e.x] + p[e.y] / du[e.y]

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#define N 501
#define M 125000
#define eps 1e-10
using namespace std;
int n,m,cnt,a[M],b[M],st[N],to[M*2],next[M*2],du[N];
double g[N][N],f[M],ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,x,y;i<=m;i++)
{
scanf("%d%d",&x,&y);a[i]=x;b[i]=y;
to[++cnt]=y;next[cnt]=st[x];st[x]=cnt;du[x]++;
to[++cnt]=x;next[cnt]=st[y];st[y]=cnt;du[y]++;
}
for(int i=1;i<n;i++)
{
g[i][i]=1;
if(i==1) g[i][n]=1;
for(int j=st[i];j;j=next[j])
if(to[j]!=n) g[i][to[j]]=(double)-1/du[to[j]];
}
for(int i=1,k;i<n;i++)
{
k=i;while(fabs(g[k][i])<eps&&k<n) k++;
if(k==n) continue;
if(k!=i) swap(g[i],g[k]);
double t=g[i][i];
for(int j=1;j<=n;j++) g[i][j]/=t;
for(int j=1;j<n;j++)
if(i!=j)
{
t=g[j][i];
for(int k=1;k<=n;k++) g[j][k]-=g[i][k]*t;
}
}
for(int i=1;i<=m;i++)
f[i]=g[a[i]][n]/du[a[i]]+g[b[i]][n]/du[b[i]];
sort(f+1,f+m+1);
for(int i=1;i<=m;i++) ans+=f[i]*(m-i+1);
printf("%.3lf",ans);
}