這是一個期望的題目，有兩種做法。
一種是比較好想的高斯消元，另一種是思維難度稍微大了一些的數學做法，但是代碼很短，時間復雜度也更優秀。
（高斯消元做法）

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } #define N 210 int n,m; double a[N][N],p; void gauss() {for (int i=0;i<n+m+1;i++){int mx=i;for (int j=i+1;j<=n+m+1;j++)if (fabs(a[j][i])>fabs(a[mx][i])) mx=j;if (i!=mx) swap(a[i],a[mx]);for (int j=i+1;j<=n+m+1;j++){double t=a[j][i]/a[i][i];for (int k=i;k<=n+m+2;k++)a[j][k]-=t*a[i][k];}} } int main() {n=read(),m=read();cin>>p;a[0][0]=p;a[0][1]=1-p;a[0][0]--;a[0][n+m+2]--;for (int i=1;i<n+m;i++)a[i][i-1]=p,a[i][i+1]=1-p,a[i][i]--,a[i][n+m+2]--;a[n+m][n+m]=1-p;a[n+m][n+m-1]=p;a[n+m][n+m]--,a[n+m][n+m+2]--;a[n][n-1]=a[n][n+1]=a[n][n+m+2]=0;a[n+m+1][n-1]=p,a[n+m+1][n+1]=1-p,a[n+m+1][n+m+1]--,a[n+m+1][n+m+2]--;gauss();printf("%.7lf",a[n+m+1][n+m+2]/a[n+m+1][n+m+1]);return 0; }

以前沒有怎么做過期望的題目，更是沒有想到可以用高斯消元來做期望的題目。

但是現在發現其實這是個挺常見的套路，所以就學習了一下qwq

有興趣的話可以去做一下HNOI2013游走，這個也是高斯消元來求解未知數的期望類型題目。

（數學做法）

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define MAXN 110 using namespace std; long double sum[MAXN],p,ans=1.0; int n,m; int main() {cin>>n>>m;cin>>p;sum[0]=1.0;for(int i=1;i<=n+m;i++)sum[i]=sum[i-1]*(1-p)/p,ans+=sum[i];printf("%.8Lf",(1/(sum[n]/ans)));return 0; }

其實這個題有類似的題目收集郵票有興趣的話可以嘗試一下，思路很相近。

這個做法就比較玄妙了。

我們可以這樣想：

我們把狀態進行分離，因為Alice和Bob的寶石總和不變，所以我們只考慮Alice的個數，我們將狀態抽離出來為她擁有0~n+m這n+m+1種狀態，我們要計算這些狀態在總體上的期望出現次數。而這些狀態之間每次都會有概率加成的轉移。

因為游戲會進行無限輪（也就是無窮大），這樣的話開始幾次的情況其實對整體的影響很小很小。而在進行了無窮多的傳遞后，各個狀態出現的期望出現次數應該是達到了穩定值（當然這其中肯定是每輪之間是有變化的，但是要理解的一點是，我們將狀態轉移進行了無窮多輪，所以我們要從整體上來看，那么均攤到每個狀態的概率肯定是穩定的、恒定的）

既然每種狀態的概率是穩定的，那么我們考慮每次狀態的轉移。考慮狀態\(A_k\)和它的上一個狀態\(A_{k-1}\)，\(A\)每次有p的概率轉移到上一個狀態，它的上一個狀態有1-p的概率轉移到它。但是要維持在總體上他們的穩定，那么就有\(A_k\times p=A_{k-1}\times (1-p)\)，這樣的話我們可以知道這些狀態的分布呈公比為\(\frac{1-p}{p}\)的等比數列。那么我們假設開始的0狀態為單位1，就可以進行遞推了。

隨后我們可以用\(A_n\)狀態來除以總數，算出在這些狀態中（如果把總和看作單位1的話），n狀態出現的次數（比1小）。最后我們將整個游戲的無數個回合具象成一條直線。那么n狀態就是上面的一些間隔的點。我們要求的問題也可以轉化成相鄰兩個n狀態出現的間隔。那么就用1來除以它就可以了。

轉載于:https://www.cnblogs.com/fengxunling/p/9763816.html

總結

以上是生活随笔為你收集整理的游戏（期望）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。