概率期望小结

从一开始就觉得期望和概率很难，现在也是。应该是因为这个玩意儿比较抽象吧，来几道简单例题。

T1

• 在陆地花费的时间是固定的，那么它对期望的贡献当然也是本身啦。
• 考虑在通过河的时候，最好的情况是船正好向你走来，那么你花费的时间是\\(\\frac{L}{v}\\)，最坏的呢？此时船刚向对面走去，那么花费的时间为\\(\\frac{3L}{v}\\)。我们求期望，一般有两种方法：1、直接定义期望，递推求解。 2、利用期望的线性性， 枚举所有情况求。 本题来说，因为所有情况概率相等，并且没有确定的值，所以我们考虑枚举所有情况列式子。其实一看就可以看出来，虽然情况是无穷无尽的，但是平均数一定是\\(\\frac{2L}{v}\\)。那么期望自然就是平均值喽。

T2

• 前言：bzoj找不到这道题了，其实就是luogu上的绿豆蛙的归宿。
• 看完题目脑子里出来一个思路，直接从1号点走，每次走到一个点，转移一下。呵呵，当然是错误的啦。为什么呢？考虑期望的定义，一条边对答案的贡献是它被使用的概率*权值。而如果我们正着推，每个边在最后乘上的概率是不正确的。画个图好好想一想。如何解决这个问题？只需要我们倒着递推就好了。
• 设\\(f[i]\\)表示从i到n的期望长度，那么\\(f[x]=\\frac{\\sum f[y]+edge(x,y)}{k}\\)。最终答案就是\\(f[1]\\)。你倒着建图跑拓扑或者直接记忆化搜索都可以。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+100;
int n,m,tot,ver[N<<1],Next[N<<1],lin[N],edge[N],cd[N];
double f[N];bool v[N];
void add(int x,int y,int z){ver[++tot]=y;Next[tot]=lin[x];lin[x]=tot;edge[tot]=z;cd[x]++;}
void dfs(int x){
    if(x==n){
        f[x]=0;return ;
    }
    if(v[x]) return ;
    v[x]=1;double temp=0;
    for(int i=lin[x];i;i=Next[i]){
        int y=ver[i];
        //if(v[y]) continue;
        dfs(y);
        f[x]+=1.0*(edge[i]+f[y])/cd[x];
    }
}
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);
    }dfs(1);
    printf(\"%.2lf\",f[1]);
    return 0;
}

T3

• 这题没有什么明确终止状态，枚举所有情况啥的，不太好算吧。
• 考虑直接定义期望，设\\(f[i]\\)表示到了第i秒，电梯上人的期望数量。那么\\(f[i]=(f[i-1]+1)*p+f[i-1]*(1-p)\\)。貌似没什么问题？呵呵，样例都没过去……还有，其实没必要这样递推吧，直接\\(n*p\\)不好了。
• 它错到哪里了？当T<=n的时候，这样求是没有问题的。问题就在，有可能你电梯上人已经超过n了，你求期望的时候还在求。所以，我们不能这样求。其实只需要多加一维的状态就好保证状态合法了吧？但是你加一维状态表示人数，肯定期望数量是求不了的啊。那就求概率呗。然后利用期望的定义，求期望。
• \\(f[i][j]\\)表示到了第i秒，电梯上有j个人的概率。\\(f[i][j]=f[i-1][j-1]*p+f[i-1][j]*(j==n?1:(1-p))\\)。最后，\\(ans+=f[t][j]*j\\)就完事了。

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int n,t;double p,ans,dp[N][N];
int main(){
    scanf(\"%d%lf%d\",&n,&p,&t);
    dp[0][0]=1;
    for(int i=1;i<=t;++i){
        for(int j=0;j<=min(i,n);++j){
            if(j!=n)
            dp[i][j]=dp[i-1][j-1]*p+dp[i-1][j]*(1-p);
            else
            dp[i][j]=dp[i-1][j-1]*p+dp[i-1][j];
        }
    }
    for(int i=0;i<=min(t,n);++i) ans+=dp[t][i]*i;
    printf(\"%.7lf\\n\",ans);
    return 0;
}

暂时先更新到这里。
还有其他的，以后总结。