注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

POJ 1487  

2010-07-27 22:35:21|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
就是根据题意依次遍历,对于循环出现的其实就是利用高斯消元来接,比如a=(a 1 a)就是说a=1/3*a+1/3+1/3*a来求解,并且注意句意分析,利用递归来分解,注意要求两个解,一个是期望,一个是停止的概率,看是否等于1
这是以前的regional的原题,有数据:http://www.informatik.uni-ulm.de/acm/Regionals/1998/input/
#include<cstdio>
#include<cstring>
#include<cmath>
#define eps 1e-7
double a[30][30],b[30];
int n,d,qq=1,c[30];
char q[5000];
void init(int l,int r,double now){
int t=0,k=0,tmp,p1,p2,mark=1;
for(int i=l;i<=r;++i){
if(q[i]>='0'&&q[i]<='9'){
++k;
while(q[i+1]>='0'&&q[i+1]<='9')
++i;
}
if(q[i]=='('){
++k;
while(!(t==1&&q[i]==')')){
if(q[i]=='(')
++t;
if(q[i]==')')
--t;
++i;
}
t=0;
}
if(q[i]>='a'&&q[i]<='z')
++k;
}
tmp=k;
for(int i=l;i<=r;++i){
if(q[i]=='-')
mark=-1;
if(q[i]>='0'&&q[i]<='9'){
k=q[i]-'0';
while(q[i+1]>='0'&&q[i+1]<='9'){
k=k*10+q[i+1]-'0';
++i;
}
a[d][n]+=mark*now*k/tmp;
a[d][n+1]+=now/tmp;
mark=1;
}
if(q[i]=='('){
++k;p1=i+1;
while(!(t==1&&q[i]==')')){
if(q[i]=='(')
++t;
if(q[i]==')')
--t;
++i;
}
init(p1,i,now/tmp);
t=0;
}
if(q[i]>='a'&&q[i]<='z')
a[d][q[i]-'a']-=now/tmp;
}
}
int gauss(){
int i,j;
memset(c,0,sizeof(c));
for(i=0,j=0;i<n,j<n;++i,++j){
int tt=i;
for(int k=i+1;k<n;++k)
if(fabs(a[k][j])>fabs(a[tt][j]))
tt=k;
for(int j0=0;j0<=n+1;++j0){
double temp=a[i][j0];
a[i][j0]=a[tt][j0];
a[tt][j0]=temp;
}
if(fabs(a[i][j])<eps){
c[j]=1;
//--i;
continue ;
}
for(int k=0;k<n;++k)
if(k!=i){
double tmp=a[k][j]/a[i][j];
for(int j0=0;j0<=n+1;++j0)
a[k][j0]-=a[i][j0]*tmp;
}
}
for(int k=i;k<n;++k)
if(fabs(a[k][n])>eps||fabs(a[k][n+1])>eps)
return 0;
for(int i0=0;i0<n;++i0)
if(!c[i0]){
b[i0]=a[i0][n]/a[i0][i0];
if(fabs(a[i0][n+1]/a[i0][i0]-1)>eps)
c[i0]=1;
}
return 1;
}
int main(){
while(scanf("%d",&n),n){
for(int i=0;i<n;++i)
for(int j=0;j<n+2;++j)
a[i][j]=0;
for(d=0;d<n;++d){
getchar();
scanf("%[^\n]",&q);
int w=0;
while(q[w]!='(')
++w;
a[d][d]=1;
init(w+1,strlen(q)-1,1);
}
printf("Game %d\n",qq++);
int ret=gauss();
if(ret==0){
puts("?");
continue ;
}
for(int i=0;i<n;++i){
if(c[i])
printf("Expected score for %c undefined\n",(char)('a'+i));
else printf("Expected score for %c = %.3f\n",(char)('a'+i),b[i]);
}
printf("\n");
}
return 0;
}
  评论这张
 
阅读(809)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018