/**//* 题意:父亲有f元、母亲有m元,盒子里有nb个蓝球,nr个红球 每次取一个球,蓝球的话父亲赢母亲1元,红球的话。。。 球会放回,问游戏结束的期望 设E[i]表示父亲现在有i元离游戏结束还需要的次数的期望 有E[i] = pf*E[i+1]+pm*E[i-1]+1 E[f+m]=E[0]=0 E[i]与E[i-1],E[i+1]有关 我们求的是E[f] 可以知道有环。有环的话类似zoj3329 用E[f]去表示其他 最后再得到E[f] = F(E[f]) E[i] = x[i]E[f]+y[i] 但算不出 表示成e[i] = a[i]e[f]+b[i]e[i+1]+c[i] 最后再修改一下!!
高斯消元需要O(n3) n<=10000 TLE */ #include<cstdio> #include<cstring>
const int MAXN = 20010;
double a[MAXN],b[MAXN],c[MAXN];
int main() { int T; for(scanf("%d",&T);T--;) { int f,m,nb,nr,fm; scanf("%d%d%d%d",&f,&m,&nb,&nr); double pm = nr/(nb+nr+0.0),pf = 1 - pm; fm = f+m;
//由于有环,尝试用e[f]去表示其他 e[i] = a`[i]e[f]++c`[i] //如果直接这样表示还不能算出来 //再设e[i] = a[i]e[f]+b[i]e[i+1]+c[i] //这样就比较容易算了 lyd Orz //林宇东 20:47:26 //加b[i]是手段,只是在想怎么表示e[i+1],然后再把它去掉
a[f] = 1.0,b[f] = c[f] = 0.0; a[0] = b[0] = c[0] = 0.0; a[fm] = b[fm] = c[fm] = 0.0;
//e[i] = a[i]e[f]+b[i]e[i+1]+c[i] for(int i=f+1;i<fm;i++) { double tmp = 1-pm*b[i-1]; a[i] = a[i-1]*pm/tmp; b[i] = pf/tmp; c[i] = (1+pm*c[i-1])/tmp; } //e[i] = a`[i]e[f]+c[i] for(int i = fm-1;i>f;i--) { a[i]+=b[i]*a[i+1]; c[i]+=b[i]*c[i+1]; } //e[i] = a[i]e[f]+b[i]e[i-1]+c[i] for(int i=f-1;i;i--) { double tmp = 1-pf*b[i+1]; a[i] = a[i+1]*pf/tmp; b[i] = pm/tmp; c[i] = (1+pf*c[i+1])/tmp; } //e[i] = a`[i]e[f]+c[i] for(int i = 1;i<f;i++) { a[i]+=b[i]*a[i-1]; c[i]+=b[i]*c[i-1]; } printf("%.0f\n",(1+pm*c[f-1]+pf*c[f+1])/(1-pm*a[f-1]-pf*a[f+1])); } return 0; }
/**//* 网上还提供另外的做法 E[i] = pm*E[i-1]+pf*E[i+1]+1 整理,列出增广矩阵 发现每一行只有3个系数-pm , 1 , -pf , 1 所以先从上到下消去对角线下的,再从下到上消去对角线上的即可了O(n)
有通用的方法:追赶法 */
#include<cstdio>
const int MAXN = 20010;
double a[MAXN],b[MAXN],c[MAXN],d[MAXN];
int main() { int T; for(scanf("%d",&T);T--;) { int f,m,fm,nb,nr; scanf("%d%d%d%d",&f,&m,&nb,&nr); fm = f+m; double pm = nr/(nr+nb+0.0) , pf = 1-pm; b[0]=1.0,a[0]=c[0]=d[0]=0.0; b[fm]=1.0,a[fm]=c[fm]=d[fm]=0.0; for(int i=1;i<fm;i++) { double k = -pm/b[i-1]; d[i]=1.0-d[i-1]*k; b[i]=1.0-c[i-1]*k; c[i]=-pf; } for(int i=fm-1;i>=f;i--) { double k = c[i]/b[i+1]; d[i]-=d[i+1]*k; } printf("%.0f\n",d[f]/b[f]); } return 0; }
列出方程后,高斯消元O(n^3)太慢了,而且精度损失也比较大 所以题目给出的应该不是用高斯消元吧~~~挖掘方程的特点 hit 2914 zoj3329 都是方程有环的,都将要求的变量看成未知量,然后去表示其他,E[i] = fx(i) 最后推到自己E[x] = fx(x)
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|