題目：給出n個數，分為兩個集合， 可以為空。 第一個集合，數值異或為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<iostream> #include<cstdio> #include<map> #include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<set> #include<string> #include<queue> #include<bitset> #define inf 1<<30 #define M 2005 #define N 100000 #define maxn 300005 #define eps 1e-10 #define zero(a) fabs(a)<eps #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<bitset<N> >a; vector<int>b; //equation a*x=b LL num[N]; int n,cnt[62]; int important[62]; int ans[N]={0}; void add(bitset<N>A,int B){ int m=a.size(); for(int i=0;i<m;i++){ if(A[important[i]]){ A^=a[i]; B^=b[i]; } } int idx=-1; for(int i=0;i<n;i++) if(A[i]){ idx=i; break; } if(idx==-1) return ; important[m]=idx; for(int i=0;i<m;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<n;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)){ bitset<N>t; t.reset(); for(int j=0;j<n;j++) t[j]=(num[j]>>i)&1; add(t,1); } } //odd for(int i=61;i>=0;i--){ if(cnt[i]&&(cnt[i]&1)){ bitset<N>t; t.reset(); for(int j=0;j<n;j++) t[j]=(num[j]>>i)&1; add(t,0); } } for(int i=0;i<a.size();i++){ ans[important[i]]=b[i]; } for(int i=0;i<n;i++) printf("%d%c",2-ans[i],i==n-1?'\n':' '); return 0; } #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<set> #include<string> #include<queue> #include<bitset> #define inf 1<<30 #define M 2005 #define N 100000 #define maxn 300005 #define eps 1e-10 #define zero(a) fabs(a)<eps #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<bitset<N> >a; vector<int>b; //equation a*x=b LL num[N]; int n,cnt[62]; int important[62]; int ans[N]={0}; void add(bitset<N>A,int B){ int m=a.size(); for(int i=0;i<m;i++){ if(A[important[i]]){ A^=a[i]; B^=b[i]; } } int idx=-1; for(int i=0;i<n;i++) if(A[i]){ idx=i; break; } if(idx==-1) return ; important[m]=idx; for(int i=0;i<m;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<n;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)){ bitset<N>t; t.reset(); for(int j=0;j<n;j++) t[j]=(num[j]>>i)&1; add(t,1); } } //odd for(int i=61;i>=0;i--){ if(cnt[i]&&(cnt[i]&1)){ bitset<N>t; t.reset(); for(int j=0;j<n;j++) t[j]=(num[j]>>i)&1; add(t,0); } } for(int i=0;i<a.size();i++){ ans[important[i]]=b[i]; } for(int i=0;i<n;i++) printf("%d%c",2-ans[i],i==n-1?'\n':' '); return 0; }
