HDU3032 Nim or not Nim

/*
*State: 
*题目大意：
*        Alice和Bob轮流取N堆石子，每堆S[i]个，Alice先，
*        每一次可以从任意一堆中拿走任意个石子，也可以将
*        一堆石子分为两个小堆。先拿完者获胜。(1 ≤ N ≤ 10^6,
*        1 ≤ S[i] ≤ 2^31 - 1)
*解题思路：
*        找sg规律。
*解题感想：
*        一看数据规模就知道sg不靠谱，应该是规律型的。
*        自己用笔模拟了大半天，模拟得蛋疼了之后干脆写成
*        代码吧，结果计算机一算就是靠谱些（用笔还模拟错了，
*        怪不得一开始没有找对规律），计算机是个好东西啊。
*/
//下面这一段用来打表找规律的。
//前三十组的sg值，很容易找出规律
/*
sg[0]: 0
sg[1]: 1
sg[2]: 2
sg[3]: 4
sg[4]: 3
sg[5]: 5
sg[6]: 6
sg[7]: 8
sg[8]: 7
sg[9]: 9
sg[10]: 10
sg[11]: 12
sg[12]: 11
sg[13]: 13
sg[14]: 14
sg[15]: 16
sg[16]: 15
sg[17]: 17
sg[18]: 18
sg[19]: 20
sg[20]: 19
sg[21]: 21
sg[22]: 22
sg[23]: 24
sg[24]: 23
sg[25]: 25
sg[26]: 26
sg[27]: 28
sg[28]: 27
sg[29]: 29
*/

打表代码：

View Code

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int MAX = 1005;
 5 int sg[MAX];
 6 bool vst[MAX];
 7 
 8 void take_part(int n)
 9 {
10     for(int i = 1; i <= n / 2; i++)
11     {
12         int yihuo = 0;
13         yihuo ^= sg[i] ^ sg[n - i];
14         vst[yihuo] = true;
15     }
16 }
17 
18 void get_sg()
19 {
20     memset(sg, 0, sizeof(sg));
21     for(int i = 0; i < MAX; i++)
22     {
23         memset(vst, false, sizeof(vst));
24         int j = 0;
25         while(j++ < i)
26         {
27             vst[sg[j]] = true;
28         }
29         take_part(i);
30         for(int j = 0; j < MAX; j++)
31         {
32             if(!vst[j])
33             {
34                 sg[i] = j;
35                 break;
36             }
37         }
38     }
39     return ;
40 }
41 
42 void view_arr(int a[], int n)
43 {
44     for(int i = 0; i < n; i++)
45     {
46         cout << "sg[" << i << "]" << ": " << a[i] << endl;
47     }
48     return ;
49 }
50 
51 int main(void)
52 {
53     int cas;
54     get_sg();
55     view_arr(sg, 30);
56     return 0;
57 }

ac代码：

View Code

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int get_sg(int n)
 5 {
 6     if(n == 0)
 7         return 0;
 8     
 9     int remain = n % 4;
10     if(remain == 0)
11         return n - 1;
12     else if(remain == 3)
13         return n + 1;
14     else 
15         return n;
16 }
17 
18 int main(void)
19 {
20     int cas;
21     scanf("%d", &cas);
22     while(cas--)
23     {
24         int n, yihuo = 0;
25         scanf("%d", &n);
26         for(int i = 0; i < n; i++)
27         {
28             int pile, tmp;
29             scanf("%d", &pile);
30             tmp = get_sg(pile);
31             yihuo ^= tmp;
32         }
33         if(!yihuo)
34             printf("Bob\n");
35         else
36             printf("Alice\n");
37     }
38 
39     return 0;
40 }