Problem
Solution
首先我们要知道:第一个人只要挑选出一些元素 $a_i$ 后,使得剩下这个集合 $A$ 的异或空间的张成不包含 $0$,则先手必赢。(异或和不为 $0$,NIM游戏先手必赢)
换言之,先手只要选对了,后手怎么选,先手都可以赢。那么先手怎么选才是对的呢?
选出一个极大的线性无关子集(异或空间下)。(这不恰恰是线性基能做的事吗?)
在满足上面这个条件下,要求选出来的元素和最小。因此我们直接贪心地将 $A$ 集合从大到小排序,插入线性基。无法插入的元素即是我们要拎出来的元素,加入答案。留下来的集合就是原集合的极大的线性无关子集(异或空间下)。
Code
Talk is cheap.Show me the code.
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
int x=0,f=1; char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
const int N = 107;
int n,ans;
int a[N];
struct LB {
int d[N];
int insert(int x) {
int tmp = x;
for(int i=31;i>=0;--i) {
if((1<<i) & x) {
if(d[i]) {
x ^= d[i];
} else {
d[i] = x; return 0;
}
}
}
return tmp;
}
}B;
bool cmp(int a,int b) {
return a > b;
}
signed main()
{
n = read();
for(int i=1;i<=n;++i)
a[i] = read();
sort(a+1, a+1+n, cmp);
for(int i=1;i<=n;++i) {
int val = B.insert(a[i]);
ans += val;
}
printf("%lld\n",ans);
return 0;
}
这解法,过于优秀了,我的高斯消元写起来那么费劲