0条评论
还没有人评论过~
k<=100
根据$Nim$游戏,如果这些石子个数异或和为$0$则先手必败,所以我们需要给对方留下不存在异或和为$0$的子集的石子堆,这就是极大线性基...
我们把元素从大到小排序,每次贪心地把当前元素加入线性基如果可以加入则加入否则消去,最后需要拿走的就是那些被消成$0$的石子堆...
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> //by NeighThorn using namespace std; const int maxn=100+5; int n,a[maxn],b[maxn],c[maxn]; long long ans; inline bool cmp(int x,int y){ return x>y; } inline void xor_gauss(void){ for(int i=1;i<=n;i++){ for(int j=31;j>=0;j--) if((a[i]>>j)&1){ if(c[j]) a[i]^=c[j]; else{ c[j]=a[i]; break; } } if(a[i]) ans-=b[i]; } } signed main(void){ scanf("%d",&n);ans=0LL; for(int i=1;i<=n;i++) scanf("%d",&a[i]),ans+=a[i]; sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) b[i]=a[i]; xor_gauss(); printf("%lld\n",ans); return 0; }
By NeighThorn
来源:https://www.cnblogs.com/neighthorn/p/6431776.html