HDU 3032 （SG打表找规律）

题意：

有n堆石子，alice先取，每次可以选择拿走一堆石子中的1~x(该堆石子总数) ，也可以选择将这堆石子分成任意的两堆。alice与bob轮流取，取走最后一个石子的人胜利。

思路：

因为数的范围比较大，所以最好通过SG打表的结果找出规律在解。

sg(4k+1)=4k+1;sg(4k+2)=4k+2;sg(4k+3)=4k+4; sg(4k)=4k-1;

1 2 4 3 5 6 8 7

Sample Input
2
3
2 2 3
2
3 3

Sample Output
Alice
Bob

SG打表找规律

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <string>
 6 # include <cmath>
 7 # include <queue>
 8 # include <list>
 9 # define LL long long
10 using namespace std ;
11 
12 
13 int sg[1010];
14 bool vis[1010];
15 
16 int mex(int n) //求N的SG值
17 {
18     if(sg[n] != -1)return sg[n];
19     memset(vis,false,sizeof(vis));
20     for(int i=n-1;i>=0;i--)
21     {
22         vis[mex(i)]=1;
23     }
24     for(int i=1;i<=n/2;i++)
25     {
26         vis[mex(i)^mex(n-i)]=1;
27     }
28     for(int i = 0;;i++)
29         if(vis[i] == false)
30         {
31             sg[n] = i;
32             break;
33         }
34     return sg[n];
35 }
36 
37 int main()
38 {
39 
40     memset(sg,-1,sizeof(sg));
41     for(int i = 0;i <= 200;i++)
42         sg[i] = mex(i);
43     int t , n ,x ;
44 
45        for(int i=0;i<=100;i++)
46        {
47           cout<<sg[i]<<" ";
48           if(i%10==0)
49             cout<<endl;
50        }
51 
52     return 0;
53 }

View Code

题解代码

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std ;
 5 
 6 
 7 int main ()
 8 {
 9     int T ;
10     scanf("%d" , &T) ;
11     while(T--)
12     {
13         int n ;
14         scanf("%d" , &n) ;
15         int x ;
16         int sum = 0 ;
17         while(n--)
18         {
19             scanf("%d" , &x) ;
20             if (x % 4 == 1)
21               sum ^= x ;
22             else if (x % 4 == 2)
23               sum ^= x ;
24             else if (x % 4 == 3)
25               sum ^= (x+1) ;
26             else 
27               sum ^= (x-1) ;
28         }
29         if (sum == 0)
30           printf("Bob
") ;
31         else
32           printf("Alice
") ;
33     }
34     
35     
36     return 0 ;
37 }

View Code