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

ydc的博客

 
 
 

日志

 
 

CTSC 2013 猴子 闲扯  

2014-03-15 22:01:34|  分类: ctsc |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
首先2^(3n)高斯消元是裸的
考虑优化……打表可以发现,设f(S)表示局面S的胜率,若A∩B=?,A∪B=S,则f(S)=f(A)+f(B)
证明见cxm题解
然后就没了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 110
using namespace std;
int n,m;
double mat[maxn][maxn],prob[maxn][maxn],x[maxn];
void read()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%lf",&prob[i][j]);
for(int i=1;i<n;++i)
{
mat[i][i]=1;
for(int j=1;j<=n;++j)
if(i!=j)
{
mat[i][i]=mat[i][i]-prob[i][j]/(n-1);
mat[i][j]=mat[i][j]-prob[i][j]/(n-1);
}
}
fill(mat[n]+1,mat[n]+n+2,1.0);
}
void Gauss()
{
for(int i=1;i<=n;++i)
{
int k=i;
for(int j=i+1;j<=n;++j)
if(abs(mat[j][i])>abs(mat[k][i]))
k=j;
if(k!=i)
for(int j=i;j<=n+1;++j)
swap(mat[k][j],mat[i][j]);
for(int j=i+1;j<=n;++j)
{
double val=mat[j][i]/mat[i][i];
for(int k=i;k<=n+1;++k)
mat[j][k]=mat[j][k]-mat[i][k]*val;
}
}
x[n]=mat[n][n+1]/mat[n][n];
for(int i=n-1;i>=1;--i)
{
x[i]=mat[i][n+1];
for(int j=n;j>i;--j)
x[i]=x[i]-mat[i][j]*x[j];
x[i]/=mat[i][i];
}
}
void Query()
{
static char str[maxn];
for(int i=1;i<=m;++i)
{
scanf("%s",str+1);
double ans=0;
for(int j=1;j<=n;++j)
if(str[j]=='1')
ans+=x[j];
printf("%.8f\n",ans);
}
}
int main()
{
read();
Gauss();
Query();
return 0;
}

  评论这张
 
阅读(373)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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