QUESTION
Given n integers {a1, a2, ..., an}, n ≤ 100, 000. Select some, s.t. they have the maximum xor sum.
For random numbers like 19, 44, 9, 33, they could be made into lines like:
0 1 0 0 1 1
1 0 1 1 0 0
0 0 1 0 0 1
1 0 0 0 0 1
The algorithm is selecting the "1" "0" from high to low order ( left to right ), then from up to down.
We need var "int ans" for storing the final answer.
Once we find the first "1" in the column (the number we found called "x"), we let the number xor the number below which have got "1" in the same column.
Then, we let x xor ans iff ans has "0" at the current column. And we let the number x = 0 0 0 0 0 ......( x = 0 [C++])
Loop it in every column till the last one.
CODE:
//origin code by cmd2001
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int in[10100], n, ans, x;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", in + i);
x = 0;
for (int i = 31; i >= 0; i--) {
x = 0;
for (int j = 1; j <= n; j++) {
if ((in[j] >> i) & 1) x = j;
} if (x) {
for (int j = 1; j <= n; j++) {
if (j != x && (in[j] >> i) & 1) in[j] ^= in[x];
}
if (!(ans >> i) & 1) ans ^= in[x];
in[x] = 0;
}
}
printf("%dn", ans);
return 0;
}
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
