题面
BZOJ https://www.lydsy.com/JudgeOnline/problem.php?id=1299
题解
\(Nim\) 博弈的变形形式.
显然, 如果我们不考虑拿巧克力棒出来的话, 这就是一个裸的 \(Nim\) 博弈.
但是现在可以加入巧克力棒. 加入巧克力棒的意义是修改当前的异或和.
如果不能够改变当前先后手赢的状态的话, 那么必定不能够拿出一个巧克力棒的集合满足异或和为 \(0\).
初始情况下是先手必败的情况, 因为先后不改变当前的必胜 / 必败情况, 所以先手必须要拿出一个异或和为 \(0\) 的集合, 并且使得剩下的部分不能够存在异或和为 \(0\) 的子集. 不难证明如果剩下部分存在一个异或和为 \(0\) 的子集的话, 必定也可以把这个子集拿出来使得不存在子集使得异或和为 \(0\).
那么, 唯一需要判定的只剩下是否存在一个子集使得异或和为 \(0\) 了. 直接线性基即可.
时间复杂度 \(O(Tnlog)\), 所以 \(n\) 其实想出多大出多大, 因为线性基内的元素个数最多不会超过 \(log\) 个, 否则必定会出现线性相关, 即存在一个子集满足异或和为 \(0\).
也就是说, 真正的时间复杂度其实是 \(O(Tmin(n,log)log)\) 的, 当 \(n\) 较大的时候瓶颈在于读入.
然而这题 \(n\) 小得可怜, 直接暴力 \(dfs\) 都是可以的.
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<cmath>
- #include<algorithm>
- using namespace std;
- #define ll long long
- #define MAX 15
- inline int read()
- {
- int x=0;bool t=false;char ch=getchar();
- while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
- if(ch=='-')t=true,ch=getchar();
- while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
- return t?-x:x;
- }
- struct xxj
- {
- int p[31];
- bool insert(int x)
- {
- for(int i=30;~i;--i)
- if(x&(1<<i))
- {
- if(!p[i]){p[i]=x;return true;}
- x^=p[i];
- }
- return false;
- }
- void clear(){memset(p,0,sizeof(p));}
- }G;
- int n,a[MAX];
- int main()
- {
- int T=10;
- while(T--)
- {
- n=read();
- for(int i=1;i<=n;++i)a[i]=read();
- G.clear();bool fl=false;
- for(int i=1;i<=n;++i)
- if(!G.insert(a[i]))fl=true;
- puts(fl?"NO":"YES");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2729206.html