首页 > 代码库 > BZOJ 3105 新Nim游戏
BZOJ 3105 新Nim游戏
注意到线性基的非空子集的异或都不是0。
我们的目的就是消出这样一个线性基,是对面再怎么拿,异或和都是1。
从大到小排序消就好了
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 105 using namespace std; long long n,a[maxn],b[maxn],bit[32],ans=0,sum=0; bool vis[32]; bool cmp(long long x,long long y) { return x>y; } int main() { scanf("%lld",&n); for (long long i=1;i<=n;i++) {scanf("%lld",&a[i]);sum+=a[i];} sort(a+1,a+n+1,cmp); for (long long i=1;i<=n;i++) b[i]=a[i]; for (long long i=1;i<=n;i++) for (long long k=31;k>=0;k--) { if (!(a[i]&(1<<k))) continue; if (!vis[k]) {vis[k]=true;ans+=b[i];bit[k]=a[i];break;} else a[i]^=bit[k]; } printf("%lld\n",sum-ans); return 0; }
BZOJ 3105 新Nim游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。