题意:给出n堆石子,每次可以把第 i 堆取出1个石子,选择第 j 队和第 k 堆放入一个石子,i<j<=k。两人轮流操作,最后不能操作的输,两人均采用最佳策略
如果先手能获胜,则输出先手第一步选取的 i , j , k (如有多解,则输出字典序最小的答案)否则输出 -1,-1,-1;
我们按照从左往右分别把堆编号成 n-1,n-2,n-3 ...... ,0。取出1个第 n-i 堆的石子之后,只能在小于 n-i 的堆中选出两堆 j,k放入1个石子(j==k时,即往 j 堆放入2个石子)
那么 i 的后继状态就是 j和k。最终,所有的石子都会到第0堆中,我们把单个石子的胜负看成一个游戏,那么sg[i]=mex{ sg[ j ]^sg[ k ] | i<j<=k };整个游戏的胜负就是所有游戏的sg函数值
的异或和。接着我们枚举 i,j,k找出答案
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int vis[1024],sg[24]; 5 void init() 6 { 7 int i,j,k; 8 for(i=0;i<24;i++) 9 { 10 for(j=0;j<i;j++) 11 { 12 for(k=0;k<=j;k++) 13 { 14 vis[sg[j]^sg[k]]=1; 15 } 16 } 17 for(j=0;j<1024;j++) 18 { 19 if(vis[j]==0) 20 { 21 sg[i]=j; 22 break; 23 } 24 } 25 memset(vis,0,sizeof(vis)); 26 } 27 } 28 int a[24]; 29 int main() 30 { 31 init(); 32 int i,j,k,n,Xor,cas=1; 33 while(~scanf("%d",&n)) 34 { 35 if(n==0) 36 break; 37 Xor = 0; 38 for(i=0;i<n;i++) 39 { 40 scanf("%d",&a[i]); 41 //sg[i]^sg[i]==0 42 if(a[i]%2==1) 43 Xor=Xor^sg[n-i-1]; 44 } 45 if(Xor==0) 46 { 47 printf("Game %d: -1 -1 -1\n",cas++); 48 } 49 else 50 { 51 int flag=0; 52 for(i=0;i<n;i++) 53 { 54 if(a[i]==0) 55 continue; 56 for(j=i+1;j<n;j++) 57 { 58 for(k=j;k<n;k++) 59 { 60 if((Xor^sg[n-i-1]^sg[n-j-1]^sg[n-k-1])==0) 61 flag=1; 62 if(flag==1) 63 break; 64 } 65 if(flag==1) 66 break; 67 } 68 if(flag==1) 69 break; 70 } 71 printf("Game %d: %d %d %d\n",cas++,i,j,k); 72 } 73 } 74 }