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

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

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

 
 
 

日志

 
 

HOJ 2645  

2010-08-30 23:11:54|  分类: hoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一道很不错的博弈题,一般的博弈是说当所有子游戏都达到最终态时游戏结束,而这个题是说有一些中间态,但到达这些状态,游戏立即结束,所以博弈的双方都不会转移到这样局面上,不然自己会立即失败(除非迫不得已转移),所以这些状态直接无视掉就可以了,对应这个题,就可以用容斥原理来去掉那些状态,然后异或出结果就可以了
#include<cstdio>
#include<cstring>
const int mm=1000000000;
int t,n,m,a[100],p[10],k,b[100];
long long gcd(long long a,long long b){
if(b==0)
return a;
return gcd(b,a%b);
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&m,&n);
for(int i=0;i<m;++i)
scanf("%d",&p[i]);
for(int i=0;i<n;++i){
scanf("%d",&a[i]);
b[i]=a[i];
}
int k=0;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
if(a[i]%p[j]==0)
k=1;
if(k){
printf("Xiao Hong\n");
continue ;
}
for(int i=1;i<(1<<m);++i){
long long tmp=1;
int mark=1;
for(int j=0;j<m;++j)
if(i&(1<<j)){
mark=-mark;
tmp*=p[j]/gcd(tmp,p[j]);
if(tmp>mm)
break;
}
if(tmp<=mm)
for(int j=0;j<n;++j)
b[j]+=mark*(a[j]/tmp);
}
int ans=0;
for(int i=0;i<n;++i)
ans^=b[i];
if(ans)
printf("Xiao Hong\n");
else printf("Xiao Gang\n");
}
return 0;
}
  评论这张
 
阅读(216)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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