传送门 :
思路根据 wiki,中所说的第三条线性基性质可知
线性基没有异或和为 0 的子集。
又因为 N i m Nim Nim游戏的先手获胜情况是 a [ i ] ⨁ a [ i + 1 ] . . . . = 0 a[i] \bigoplus a[i+1].... = 0 a[i]⨁a[i+1]....=0
因此我们可以将所有数都加进线性基,当出现 x = = 0 x ==0 x==0的情况就说明可以取走这个 x x x
这样子就会使得原来的集合中不存在 异 或 和 为 0 的 子 集 异或和为0的子集 异或和为0的子集正好对应性质
但是题目中还需要使得第一次取走的最少
由于异或的不进位加法性质,我们考虑从大到小的拿(原因待查,
MyCodeconst int N = 1e5+10;
ll p[N];
ll ans;
bool XXJ(ll x){
for(int i = 55 ; i>=0 ; i -- ){
if(!(x >> i ))continue;
if(!p[i]){
p[i] =x;
break;
}
x ^=p[i];
if(!x){
return false;
}
}
return true;
}
void solve()
{
int n;cin>>n;
vector a(n);
for(int i=1;i>x;a.pb(x);
}
sort(all(a),greater());
for(auto x : a){
if(!XXJ(x))
ans+=x;
}
if(ans)
cout
关注
打赏