首页 > 代码库 > BZOJ P1188 HNOI2007 分裂游戏——solution

BZOJ P1188 HNOI2007 分裂游戏——solution

2024-10-01 20:48:02   219人阅读

题目描述：

         （<--这个）

组合游戏，——把每个石头看做一个游戏，

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


联系
我们