第一个集合，数值异或为x1,第二个集合，异或为x2
要求x1+x2最大，相同的情况下x1尽量小
首先感谢xiaodao的指导。
第一步要想到的是贪心。
因为化为两个整数的和最大，我们将所有位先分离
如果n个数中，存在当前位的有m个。那么也就是当前位有m个1
如果m为偶数，且m不为0，那么肯定分为两个奇数集合，那么对于两个集合，当前位都为1，肯定为最优
如果m为奇数，则只能分为奇+偶，要求x1尽量小，肯定给1号集合偶数个。
a11*x1 ^ a12*x2 ... a1n*xn = b1
a21*x1 ^ a22*x2 ... a2n*xn = b2
...
a62_1*x1 ^ a62_2*x2^ ... a62_n*xn = b62
那么就得到这样对于每一位的方程，解出x1,x2……xn就行了
ai_j表示的是对于第j个数，第i位是1还是0
xi表示第i个数是否在第1个集合内。
注意：贪心要从高位到低位贪心
我的写法是，加入一个方程，便开始异或处理，也可以将所有的方程一起再做
不明白的地方：为什么我这样子，必须要从偶数先贪心，否则会WA，感觉这个没有影响啊，sad
难道是1+1比1+0要优秀？？？
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 1<<30
#define M 2005
#define N 100000
#define maxn 300005
#define eps 1e-10
#define zero(a) fabs(a)
#define Min(a,b) ((a)<(b) (a):(b))
#define Max(a,b) ((a)>(b) (a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson step<<1
#define rson step<<1|1
#define MOD 1000000009
#define sqr(a) ((a)*(a))
#define Key_value ch[ch[root][1]][0]
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
vector >a;
vectorb; //equation a*x=b
LL num[N];
int n,cnt[62];
int important[62];
int ans[N]={0};
void add(bitsetA,int B){
int m=a.size();
for(int i=0;i
if(A[important[i]]){
A^=a[i];
B^=b[i];
}
}
int idx=-1;
for(int i=0;i
if(A[i]){
idx=i;
break;
}
if(idx==-1) return ;
important[m]=idx;
for(int i=0;i
if(a[i][idx]){
a[i]^=A;
b[i]^=B;
}
}
a.pb(A);b.pb(B);
}
int main(){
scanf("%d",&n);
for(int i=0;i
scanf("%I64d",&num[i]);
for(int j=0;j<62;j++)
cnt[j]+=(num[i]>>j)&1;
}
//even
for(int i=61;i>=0;i--){
if(cnt[i]&&!(cnt[i]&1)){
bitsett;
t.reset();
for(int j=0;j
t[j]=(num[j]>>i)&1;
add(t,1);
}
}
//odd
for(int i=61;i>=0;i--){
if(cnt[i]&&(cnt[i]&1)){
bitsett;
t.reset();
for(int j=0;j
t[j]=(num[j]>>i)&1;
add(t,0);
}
}
for(int i=0;i
ans[important[i]]=b[i];
}
for(int i=0;i
printf("%d%c",2-ans[i],i==n-1 '\n':' ');
return 0;
}
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 1<<30
#define M 2005
#define N 100000
#define maxn 300005
#define eps 1e-10
#define zero(a) fabs(a)
#define Min(a,b) ((a)<(b) (a):(b))
#define Max(a,b) ((a)>(b) (a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson step<<1
#define rson step<<1|1
#define MOD 1000000009
#define sqr(a) ((a)*(a))
#define Key_value ch[ch[root][1]][0]