 /**//*
題意:父親有f元、母親有m元,盒子里有nb個藍球,nr個紅球
每次取一個球,藍球的話父親贏母親1元,紅球的話。。。
球會放回,問游戲結(jié)束的期望
設E[i]表示父親現(xiàn)在有i元離游戲結(jié)束還需要的次數(shù)的期望
有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]
可以知道有環(huán)。有環(huán)的話類似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;

//由于有環(huán),嘗試用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;
}

 /**//*
網(wǎng)上還提供另外的做法
E[i] = pm*E[i-1]+pf*E[i+1]+1
整理,列出增廣矩陣 發(fā)現(xiàn)每一行只有3個系數(shù)-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 都是方程有環(huán)的,都將要求的變量看成未知量,然后去表示其他,E[i] = fx(i) 最后推到自己E[x] = fx(x)
|
|
常用鏈接
隨筆分類
Links
搜索
最新評論

|
|