首页 > 代码库 > BZOJ P1188 HNOI2007 分裂游戏——solution
BZOJ P1188 HNOI2007 分裂游戏——solution
题目描述:
(<--这个)
组合游戏,——把每个石头看做一个游戏,
Multi_game——消去i上的石子后,,k上的游戏又多了一个;
于是就套用multi_game的模型即可
求解SG函数时,发现一个游戏的后继是谁只与其位置有关,于是可以用一个SG值代替一堆游戏的SG值;
求解完所有SG值,后异或即可;
代码:
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 int a[25],n,sg[25],g[10010]; 5 int SG(int ); 6 int main() 7 { 8 int i,j,k,T,ans,tot; 9 scanf("%d",&T);10 while(T--){11 ans=0;tot=0;12 memset(sg,-1,sizeof(sg));13 scanf("%d",&n);14 for(i=1;i<=n;i++)15 scanf("%d",&a[i]);16 for(i=1;i<=n;i++)17 if(a[i]&1)18 ans^=SG(i);19 if(ans==0)20 printf("-1 -1 -1\n0\n");21 else{22 for(i=1;i<=n;i++)23 for(j=i+1;j<=n;j++)24 for(k=j;k<=n;k++)25 if((ans^SG(i)^SG(j)^SG(k))==0){26 if(!tot)printf("%d %d %d\n",i-1,j-1,k-1);27 tot++;28 }29 if(!tot)printf("-1 -1 -1\n");30 printf("%d\n",tot);31 }32 }33 return 0;34 }35 int SG(int x){36 int i,j;37 if(sg[x]!=-1)return sg[x];38 if(x==n)return sg[x]=0;39 memset(g,0,sizeof(g));40 for(i=x+1;i<=n;i++)41 for(j=i;j<=n;j++)42 g[SG(i)^SG(j)]=1;43 for(i=0;;i++)44 if(!g[i])return sg[x]=i;45 }
BZOJ P1188 HNOI2007 分裂游戏——solution
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。