题意:第一轮为自定义游戏，可以取走若干堆石子，也可以不取.第二轮开始为传统Nim游戏.在保证先手必胜的情况下,使得第一回合拿的火柴总数尽量小.
分析:首先我们只考虑如何保证先手必胜,因为从第二轮开始就是传统的Nim游戏了,而Nim游戏先手必胜当且仅当异或和不为0,所以我们要在第一轮构造一个局,使得第二轮一开始就是先手必胜的局面,即异或和不为0.
对于异或和不为0问题,考虑线性基.因为线性基的性质之一就是异或和不为零,所以我们只要构造出这n个数的线性基就行了,n个数中不能放入线性基的数就是我们第一轮一开始就要拿走的.
因为题目要保证第一回合拿的数尽量小,(sort)排序就好了,我们对于这n个数,从大到小构建线性基.
#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
int a[105],p[32];
inline bool get_LB(int n){
for(int i=31;i>=0;i--)
if(n>>i){
if(!p[i]){p[i]=n;break;}
else n^=p[i];
}
return n>0;
}
int main(){
LL ans=0;int n=read();
for(int i=1;i<=n;i++)a[i]=read();
sort(a+1,a+n+1);
for(int i=n;i;i--)
if(!get_LB(a[i]))ans+=a[i];
printf("%lld
",ans);
return 0;
}