题目大意
给定两个长度为 $N$ 的数列 $A,B$,要求选定一些下标 $\{k_1, k_2, \cdots , k_l \}$,使得 $ (A_{k_1}\ xor\ A_{k_2}\ xor\cdots\ xor\ A_{k_l})+(B_{k_1}\ xor\ B_{k_2}\ xor\cdots\ xor\ B_{k_l}) $ 的值最大,其中 $xor$ 表示二进制下的按位异或。请求出这个最大值。
弱化版
这道题中,我们需要同时处理两个数组,有些麻烦,那么我们先尝试解决弱化版。
给定一个长度为 $N$ 的数列 $A$,要求从中选一些数使得它们异或和最大,求这个最大值。
其实这是一个线性基板子,大家可以参考【模板】线性基,这里不再赘述。
回归本题
本题中需要处理两个数组,那么如何处理呢?
首先观察到一个性质:$0 \leq A_i,B_i \lt 2^{10}$(洛谷题目页面忘记标注了,但 AtCoder 上有)。
注意到值域非常的小,于是我们猜测时空复杂度 $O(V^2)$。这是否意味着可以把 $A,B$ 数列进行合并?
考虑如何合并:我们尝试令 $C_i = 2^{10} \times A_i + B_i$。这种做法的好处在于,它不仅合并了两个数列的信息,还将它们完整保留(例如 $C_i = A_i + B_i$ 就不能起到完整保留的作用)。
接着我们发现,题目中两数组的异或和如果也用上面方式进行转化的话,那么异或和至多只有 $2^{20}$ 个,显然是可以直接枚举的。
于是我们考虑先求出 $C$ 数组,然后把它们塞入线性基。枚举异或和然后判定它是否能用若干个 $C_i$ 异或得到(线性基基本操作),如果可以则按题目计算贡献,最后取最大值。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 25, M = 5e5 + 15;
int n, a[M], b[M], c[M], ans = 0;
int p[N];
void insert(int x) {
for (int i = 20; i >= 0; i--) {
if ((x >> i) & 1) {
if (!p[i]) { p[i] = x; break; }
else x ^= p[i];
}
}
}
bool query(int x) {
for (int i = 20; i >= 0; i--) {
if ((x >> i) & 1) {
if (!p[i]) return 0;
else x ^= p[i];
}
}
return 1;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
for (int i = 1; i <= n; i++) c[i] = (a[i] << 10) + b[i];
for (int i = 1; i <= n; i++) insert(c[i]);
for (int i = 0; i < (1 << 21); i++) {
if (!query(i)) continue;
ans = max(ans, (i >> 10) + (i % (1 << 10)));
}
printf("%d\n", ans);
return 0;
}