BZOJ1299 巧克力棒

题面：

TBL和X用巧克力棒玩游戏。每次一人可以从盒子里取出若干条巧克力棒，或是将一根取出的巧克力棒吃掉正整数长度。TBL先手两人轮流，无法操作的人输。他们以最佳策略一共进行了10轮（每次一盒）。你能预测胜负吗？

如果胜则输出"NO",否则输出"YES"

解：Nim白学.......

考虑第一个人第一步要干什么能够必胜。显然他要取出一些使得当前SG为0，且接下来对方无法取出一些使得SG仍为0。

于是把盒中^起来为0的极大集合取出来就好了。

如果不存在这样的集合那么先手必败。

线性基即可。

 1 #include <bits/stdc++.h>
 2 
 3 const int N = 20;
 4 
 5 int b[32], a[N];
 6 
 7 inline void solve() {
 8     int n;
 9     scanf("%d", &n);
10     for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
11     for(int i = 1; i <= n; i++) {
12         int x = a[i];
13         bool fd = 0;
14         for(int j = 30; j >= 0; j--) {
15             if(!((x >> j) & 1)) continue;
16             if(b[j]) x ^= b[j];
17             else {
18                 b[j] = x;
19                 fd = 1;
20                 break;
21             }
22         }
23         if(!fd) {
24             printf("NO
");
25             return;
26         }
27     }
28     printf("YES
");
29     return;
30 }
31 
32 int main() {
33     int T = 10;
34     while(T--) {
35         solve();
36         if(T) memset(b, 0, sizeof(b));
37     }
38 
39     return 0;
40 }

AC代码

我一直想的是状压取了哪些然后暴力SG.....发现并不会