题面：
TBL和X用巧克力棒玩游戏。每次一人可以从盒子里取出若干条巧克力棒，或是将一根取出的巧克力棒吃掉正整数长度。TBL先手两人轮流，无法操作的人输。 他们以最佳策略一共进行了10轮（每次一盒）。你能预测胜负吗？
如果胜则输出"NO",否则输出"YES"
解：Nim白学.......
考虑第一个人第一步要干什么能够必胜。显然他要取出一些使得当前SG为0，且接下来对方无法取出一些使得SG仍为0。
于是把盒中^起来为0的极大集合取出来就好了。
如果不存在这样的集合那么先手必败。
线性基即可。
#include <bits/stdc++.h>
const int N = ;
int b[], a[N];
inline void solve() {
int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
for(int i = ; i <= n; i++) {
int x = a[i];
bool fd = ;
for(int j = ; j >= ; j--) {
if(!((x >> j) & )) continue;
if(b[j]) x ^= b[j];
else {
b[j] = x;
fd = ;
break;
}
}
if(!fd) {
printf("NO\n");
return;
}
}
printf("YES\n");
return;
}
int main() {
int T = ;
while(T--) {
solve();
if(T) memset(b, , sizeof(b));
}
return ;
}AC代码
我一直想的是状压取了哪些然后暴力SG.....发现并不会