前言：
今天在看冯巨的期望总结，不得不说期望题就是妙！！
代码短短十几行，但思路却千奇百怪！！
今天就做一下总结（实际上题都没有做完）。
1. 期望公式：
对于互不相容的事件B，一个随机事件A：
\[P(A)=\sum_{i=1}^nP(B_i)*P(A|B_i) \]期望公式：
\[E(A)=\sum_ip_xx_i \]全期望公式：
\[E(Y)=E(E(Y|X))=\sum_iP(X==x_i)E(Y|X==x_i) \]先来一个例子：
抛一个骰子，问抛到6的期望次数：
设\(X_k\)为第K次抛到6的概率，那么\(Ans=\sum_iX_k*k\)
好的接下来就是一些例题了：
1.[SHOI2002]百事世界杯之旅
分析：
一道经典的期望题，我们考虑使用期望DP；（但是输出毒瘤）
f[i]表示得到i个瓶盖的期望次数。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int a,int b){
if(b==0){
return a;
}
return gcd(b,a%b);
}
int p=1,q=1;
int n;
int dis(int x){
int temp=x;
int cnt=0;
while(temp){
temp/=10;
cnt++;
}
return cnt;
}
signed main()
{
scanf("%lld",&n);
p=1;
for(int i=2;i<=n;i++){
int fm=(n-i+1)*q;
int fz1=p*(n-i+1);
int fz2=n*q;
int fz=fz1+fz2;
int g=gcd(fz,fm);
fz/=g,fm/=g;
p=fz;
q=fm;
}
//cout<<p<<' '<<q<<endl;
int gg=p/q;
int mother=q;
int son=p%q;
if(mother==1){
cout<<gg<<endl;
}else{
for(int i=1;i<=dis(gg);i++){
cout<<' ';
}
cout<<son<<endl;
if(gg) cout<<gg;
for(int i=1;i<=dis(mother);i++){
cout<<'-';
}
cout<<endl;
for(int i=1;i<=dis(gg);i++){
cout<<' ';
}
cout<<mother<<endl;
}
return 0;
}
2.绿豆蛙的归宿
分析：
很好的一道入门题，把期望和图论结合起来了。
由于终点确定我们考虑倒推，建反边，跑一边拓扑排序。
设f[x]是从x到n的期望长度，$$f[y]+=(f[x]+w[i])/de[y]$$
注意这里是y的入度，也就是从y会走这条路径的概率。
这里也给出顺推的方程：
g[x]是从1到i的概率
倒推：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int head[100001],to[200001],nxt[200001];
double w[200001];
int cnt;
int de[100001],in[100001];
void add(int u,int v,int z){
nxt[++cnt]=head[u];
head[u]=cnt;
to[cnt]=v;
w[cnt]=z;
}
queue<int> q;
double f[100001];
void topo()
{
q.push(n);
f[n]=0.0;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
f[v]+=(double)(w[i]+f[u])/(double)in[v];
if(!(--de[v])) q.push(v);
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add(v,u,w);
in[u]++;
de[u]++;
}
topo();
printf("%.2lf\n",f[1]);
return 0;
}
顺推：
点击查看代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int MAXX=100010;
int oud[MAXX],ind[MAXX],ver[MAXX<<1],nxt[MAXX<<1],head[MAXX],edge[MAXX<<1];
double dp[MAXX],g[MAXX];
int tot,n,m;
inline void add(int x,int y,int z){
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
edge[tot]=z;
oud[x]++;
ind[y]++;
}
inline void topsort(){
queue<int>q;
for(int i=1;i<=n;++i)if(!ind[i])q.push(i);
dp[1]=0.000;
g[1]=1.000;
while(q.size()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
dp[y]+=(dp[x]*g[x]+(double)edge[i]*g[x])/(double)oud[x];
g[y]+=g[x]/(double)oud[x];
if(--ind[y]==0)q.push(y);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;++i){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
topsort();
printf("%.2lf",dp[n]);
return 0;
}