UVALive 5760 Alice and Bob

    

 

    题意:给出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 }

 

 

   

     

 

上一篇:博弈论 SG函数 SG定理


下一篇:白书-poj2311 Cutting Game(SG函数)