NIM游戏先手必胜条件为异或值不为0,所以在第一回合我操作完后要使第二个游戏者不能删除几个堆后使其异或值为0则剩下的堆都在线性基中若有不在的数剩下第二名玩家可以使异或值为0 例如第一名玩家操作后在 5,7,9,12 线性基为1001,101,10,此线性基由5,7,9组成而12可以由此线性基组成那么第二名玩家可以将9,7取走使异或值为0,所以将堆数组降序排序后将不能进入线性基的数加起来即为答案
int n;
cin>>n;
vector<int>mp(n+1);
for(int i=1;i<=n;i++){
cin>>mp[i];
}
sort(mp.begin()+1,mp.end(),greater<int>());
int ans=0;
vector<int>st(32,0);
for(int i=1;i<=n;i++){
auto v=mp[i];
bool sy=false;
for(int j=31;j>=0;j--){
if(v&(1<<j)){
if(!st[j]){
st[j]=v;
sy=true;
break;
}
else {
v^=st[j];
}
}
}
if(!sy)ans+=mp[i];
}
cout<<ans<<endl;
记得开 long long

京公网安备 11010502036488号