概率期望小結
從一開始就覺得期望和概率很難,現在也是。應該是因為這個玩意兒比較抽象吧,來幾道簡單例題。
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; }
暫時先更新到這裡。
還有其他的,以後總結。