先看原来的游戏先手必胜条件:所有值的异或和不为零。
带回到本体,也就是两个回合之后,所有值的异或和不为零。
那么我们就不能让对方从我方已经取完的情况下还能把情况变成异或和为零。
怎么做?
等会儿,这不就是一线性基么?
只要线性基插满了,或者有个值插不下就行(进不去,怎么想都进不去。。。)
先把线性基板子打上。。。
然后看题:让第一回合拿的火柴总数尽量小。。。
如果线性基中某个位置既能是小数字,又能是大数字,那不妨就让大数字占着,把小数字留下来。
这样的贪心能保证最后答案是最优解。
至于那个。。。好像没啥用。。。
聪明的人一定能找到一种方法对吧。。。
附代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 110
using namespace std;
int n;
long long ans=0,val[MAXN],base[MAXN];
bool flag_zero=false;
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
return date*w;
}
inline bool cmp(const long long &x,const long long &y){
return x>y;
}
bool insert(long long x){
for(int i=62;~i;i--)if(x&(1LL<<i)){
if(!base[i]){base[i]=x;return false;}
else x^=base[i];
}
flag_zero=true;
return true;
}
void work(){
for(int i=1;i<=n;i++)if(insert(val[i]))ans+=val[i];
printf("%lld\n",ans);
}
void init(){
n=read();
for(int i=1;i<=n;i++)val[i]=read();
sort(val+1,val+n+1,cmp);
}
int main(){
init();
work();
return 0;
}
京公网安备 11010502036488号