洛谷P3185 *游戏

解：这个毒瘤......

我们首先发现每一堆的个数对操作不产生影响，每个操作都是针对单个石子的。

所以等价于每个石子都是一个独立的游戏。把它们异或起来作为sg函数值即可。

单个石子的sg值，直接暴力计算即可。

 1 #include <bits/stdc++.h>
 2 
 3 const int N = 110;
 4 
 5 int sg[N], bin[N], a[N];
 6 
 7 inline int check(int n) {
 8     int ans = 0;
 9     for(int i = 1; i <= n; i++) {
10         if(a[i] & 1) {
11             ans ^= sg[n - i];
12         }
13     }
14     return ans;
15 }
16 
17 inline void solve() {
18     int n, ans = 0;
19     scanf("%d", &n);
20     for(int i = 1; i <= n; i++) {
21         scanf("%d", &a[i]);
22         if(a[i] & 1) {
23             ans ^= sg[n - i];
24         }
25     }
26 
27     if(!ans) {
28         printf("-1 -1 -1
");
29         printf("0
");
30         return;
31     }
32 
33     int fd = 0;
34     ans = 0;
35 
36     for(int i = 1; i < n; i++) {
37         a[i]--;
38         for(int j = i + 1; j <= n; j++) {
39             a[j]++;
40             for(int k = j; k <= n; k++) {
41                 a[k]++;
42                 if(!check(n)) {
43                     ans++;
44                     if(!fd) {
45                         fd = 1;
46                         printf("%d %d %d
", i - 1, j - 1, k - 1);
47                     }
48                 }
49                 a[k]--;
50             }
51             a[j]--;
52         }
53         a[i]++;
54     }
55     printf("%d 
", ans);
56     return;
57 }
58 
59 int main() {
60     sg[0] = 0;
61     int n = 50;
62     for(int i = 1; i <= n; i++) {
63         for(int j = 0; j < i; j++) {
64             for(int k = 0; k <= j; k++) {
65                 bin[sg[j] ^ sg[k]] = 1;
66             }
67         }
68         for(int j = 0; ; j++) {
69             if(!bin[j]) {
70                 sg[i] = j;
71                 break;
72             }
73         }
74         memset(bin, 0, sizeof(bin));
75     }
76 
77     /*for(int i = 0; i <= n; i++) {
78         printf("%d ", sg[i]);
79     }*/
80 
81     scanf("%d", &n);
82     while(n--) {
83         solve();
84     }
85 
86     return 0;
87 }

AC代码