题目大意
给出 n 个非负整数，将数划分成两个集合，记为一号集合和二号集合。x1 为一号集合中所有数的异或和，x2 为二号集合中所有数的异或和。在最大化 x1+x2 的前提下，最小化 x1 。
输入格式
一个n 然后跟着n个10^18内的整数
输出格式
一个数字：x1
样例输入
8
1 1 2 2 3 3 4 4
样例输出
7
解题报告
令A为所有数字xor和。
考虑A的每一位
- 如果为1，则表示不管怎么分，x1和x2中一定有且仅有一个数字这个位置为1，于是我们希望x1这一位是0，对应的x2为1
- 如果为0，则表示不管怎么分，x1和x2中一定是要么两个数这一位都是1，或者两个数这一位都是0，我们希望x1这一位是1，x2这一位也是1，这样才能最大化x1+x2
我们发现我们对x2的希望很简单：根据优先级来选择1。
于是确定了优先级就可以线性基了。
0高>0低>1高>1低
我的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n, b[64], p[64], tot, a[100005];
int main() {
freopen("set.in","r",stdin);
freopen("set.out","w",stdout);
LL ans = 0;
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", a + i);
ans ^= a[i];
}
for (int i = 0; i < 64; ++i)
if (ans >> i & 1)
p[tot++] = i;
for (int i = 0; i < 64; ++i)
if (!(ans >> i & 1))
p[tot++] = i;
for (int i = 1; i <= n; ++i) {
for (int jj = 63; jj >= 0; --jj) {
int j = p[jj];
if (a[i] >> j & 1) {
if (b[j]) a[i] ^= b[j];
else {
b[j] = a[i];
for (int kk = jj - 1; kk >= 0; --kk) {
int k = p[kk];
if (b[k] && (b[j] >> k & 1)) b[j] ^= b[k];
}
for (int kk = jj + 1; kk < 64; ++kk) {
int k = p[kk];
if (b[k] >> j & 1) b[k] ^= b[j];
}
break;
}
}
}
}
for (int i = 0; i < 64; ++i) ans ^= b[i];
printf("%lld", ans);
fclose(stdin);
fclose(stdout);
return 0;
}
|