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

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

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

 
 
 

日志

 
 

POJ 3533  

2010-06-30 14:11:04|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
迄今为止,见到的最麻烦的一道博弈题,说是有1000*1000*1000的立方体,每个点上有灯,每次选择 (x1,y1,z1), (x1,y1,z2), (x1,y2,z1), (x1,y2,z2), (x2,y1,z1), (x2,y1,z2), (x2,y2,z1), (x2,y2,z2)(1 ≤ x1 ≤ x2 ≤ 1000, 1 ≤y1 ≤ y2 ≤ 1000, 1 ≤z1 ≤ z2 ≤ 1000 )点进行等状态的转换,但要求(x2,y2,z2)必须是有开着的状态,实现给你一些亮着灯的坐标,问后手是否能赢。这题要用到nim积和Tartan定理,Tartan定理说,如果G1(x1)*G2(x2)...*Gn(xn)的游戏,其中gi(xi)是第i游戏为xi时的SG函数值,那么这个游戏的SG函数值就是各个子游戏SG函数值的nim积,一维的SG函数很好求,现在再说一下nim积的求法
设Fn=2^(2^(n)),nim积有如下性质:
(1)Fi和Fj的nim积(i!=j)是Fi*Fj
(2)Fi和Fi的nim积是Fi*(3/2)
根据这个我们先设g(x,y)=2^(x)和2^(y)的nim积,则值等于2^(2^(x1)),2^(2^(x2))...2^(2^(xn)),2^(2^(y1)),2^(2^(y2))..2^(2^(ym))的nim积
然后在令f(x,y)是x和y的nim积,然后就可以利用刚才的g来求值(详情见代码),具体内容参考《GAME THEORY》
#include<cstdio>
#include<cstring>
int gg[900][900],a[1001],n,a1,a2,a3,ans;
int f(int x,int y);
int g(int x,int y){
if(gg[x][y]!=-1)
return gg[x][y];
if(!x)
return gg[x][y]=1<<y;
if(!y)
return gg[x][y]=1<<x;
int k=1,ans=1,t,x1=x,y1=y,x2=x,y2=y;
while(x||y){
t=1<<k;
if((x&1||y&1)&&!((x&1)&&(y&1)))
ans*=t;;
k<<=1;
x>>=1;
y>>=1;
}
k=1;
while(x1||y1){
t=1<<k;
if((x1&1)&&(y1&1))
ans=f(ans,t/2*3);
k<<=1;
x1>>=1;
y1>>=1;
}
return (gg[x2][y2]=ans);
}
int f(int x,int y){
if(!x||!y)
return (0);
if(x==1)
return (y);
if(y==1)
return (x);
int ans=0;
for(int i=x,k1=0;i;i>>=1,k1++)
if(i&1)
for(int j=y,k2=0;j;j>>=1,k2++)
if(j&1)
ans^=g(k1,k2);
return (ans);
}
int solve(int x){
int flag[1001];
memset(flag,0,sizeof(flag));
for(int i=1;i<x;++i)
flag[a[i]]=1;
int k=1;
while(flag[k])
++k;
return k;
}
int main(){
memset(gg,-1,sizeof(gg));
for(int i=1;i<1001;++i)
a[i]=solve(i);
while(scanf("%d",&n)!=EOF){
ans=0;
for(int i=0;i<n;++i){
scanf("%d%d%d",&a1,&a2,&a3);
ans^=f(a[a1],f(a[a2],a[a3]));
}
if(!ans)
printf("Yes\n");
else printf("No\n");
}
return 0;
}
  评论这张
 
阅读(1089)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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