本题题意很简单,给出n个人每次4人进行比赛其他人等待,胜者继续,负者排到最后,连续或得m次胜利的人成为最终的赢家,求第k个人最终获得胜利的概率是多少?
对于这题,我们首先确立一个这样的模型: x1先赢了i局,正在于x2,x3,x4赌斗,后面依次有x5,x6,……,xn等待。用P[i][j]表示x1先赢了i局的情况下,当前的xj获胜的概率。
http://acm.hdu.edu.cn/showproblem.php?pid=4326
i < m
P[i][j] = P[i + 1][j] * 1/4 + P[1][n - 2] * 3/4 j = 1
P[i + 1][n - 2] * 1/4 + P[1][1] * 1/4 + P[1][n - 1] * 2/4 j = 2
P[i + 1][n - 1] * 1/4 + P[1][1] * 1/4 + P[1][n - 1] * 1/4 + P[1][n] * 1/4 j = 3
P[i + 1][n] * 1/4 + P[1][1] * 1/4 + P[1][n] * 2/4 j = 4
P[i + 1][j - 3] * 1/4 + P[1][j - 3] * 3/4 j >=4
i = m
P[i][j] = 1 j = 1
0 j != 1
运用分数形式的高斯消元解方程。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> using namespace std; #define maxn 102 #define eps 1e-10 double g[maxn][maxn]; double x[maxn]; int n,m,k; void add(int cnt,int i,int j,double val){ int t=i*n+j; if(i==m){ if(j==1) g[cnt][n*m+1]+=-1.0*val; return; } g[cnt][t]+=val; } void gauss(int n,int m){ int row,col,i,j,k; for(row=1,col=1;row<n,col<m;row++,col++){ k=row; for(i=row+1;i<=n;i++) if(fabs(g[i][col])>fabs(g[k][col])) k=i; if(k!=row){ for(i=col;i<=m;i++) swap(g[k][i],g[row][i]); } if(fabs(g[row][col])<eps) continue; for(i=row+1;i<=n;i++){ if(fabs(g[i][col])<eps) continue; double t=g[i][col]/g[row][col]; g[i][col]=0.0; for(j=col+1;j<=m;j++) g[i][j]-=t*g[row][j]; } } for(i=n;i>=1;i--){ x[i]=g[i][m]; for(j=i+1;j<=n;j++) x[i]-=x[j]*g[i][j]; x[i]/=g[i][i]; } } int main(){ int i,j,cs,nn=0; scanf("%d",&cs); while(cs--){ scanf("%d%d%d",&n,&m,&k); memset(g,0,sizeof(g)); int cnt=0; for(i=0;i<m;i++) for(j=1;j<=n;j++){ cnt++; add(cnt,i,j,1.0); if(j==1){ add(cnt,i+1,j,-0.25); add(cnt,1,n-2,-0.75); } else if(j==2){ add(cnt,i+1,n-2,-0.25); add(cnt,1,1,-0.25); add(cnt,1,n-1,-0.5); } else if(j==3){ add(cnt,i+1,n-1,-0.25); add(cnt,1,1,-0.25); add(cnt,1,n-1,-0.25); add(cnt,1,n,-0.25); } else if(j==4){ add(cnt,i+1,n,-0.25); add(cnt,1,n,-0.5); add(cnt,1,1,-0.25); } else{ add(cnt,i+1,j-3,-0.25); add(cnt,1,j-3,-0.75); } } gauss(n*m,n*m+1); printf("Case #%d: %.6lf\n",++nn,x[k]); } return 0; }