为了方便考虑, 不妨规定只有当当前的巧克力棒都取完了, 才能拿新的巧克力棒
然后令先手第一个拿的集合为 S, 根据 nim 游戏, 当 S 的 xor 不为 0 时先手 (即原来的后手) 必胜, 又轮到先手拿集合, 那么只要一直不存在 xor 为 0 的集合, 先手最终就必败
然后当存在 xor 为 0 的集合, 那么先手必然可以做到取一个最大 xor 子集, 那么剩下的集合中一定不存在 xor 为 0 的子集(否则就可以更大), 然后就变成了先手必胜
判断是否存在 xor 为 0 的子集可以用线性基来判定(当然这个 n 太小暴力也行)
- #include<bits/stdc++.h>
- using namespace std;
- int n,x,s,a[105];
- void add(int x){
- for(int i=30;i>=0;i--)
- if (x&(1<<i))
- if (a[i])x^=a[i];
- else{
- s++;
- a[i]=x;
- break;
- }
- }
- int main(){
- for(int ii=1;ii<=10;ii++){
- scanf("%d",&n);
- s=0;
- memset(a,0,sizeof(a));
- for(int i=1;i<=n;i++){
- scanf("%d",&x);
- add(x);
- }
- if (s<n)printf("NO\n");
- else printf("YES\n");
- }
- }
- View Code
[bzoj1299]巧克力棒
来源: http://www.bubuko.com/infodetail-3282525.html