楼主尝试了一下贪心解法,从高位到低位,能异就异, 理论上应该没有问题?感谢各位巨佬!
#include <bits/stdc++.h>
using namespace std;
const int N = 3 * 1e6 + 100;
int n, q, T;
int pp = 0;
int tp[N];
int ls[N];
char s[N];
int t[N][4];
void build(int len) {
int p = 0;
for (int i = 1; i <= len; i++) {
if (!t[p][tp[i]]) {
t[p][tp[i]] = ++pp;
p = pp;
} else
p = t[p][tp[i]];
}
}
int solve(int p1, int p2, int i) {
int len = 32;
if (i == 33)
return 0;
if (t[p1][0] && t[p1][1]) {
if (t[p2][0] && t[p2][1]) {
int ret1 = solve(t[p1][1], t[p2][0], i + 1);
int ret2 = solve(t[p1][0], t[p2][1], i + 1);
return max(ret1, ret2) + (1 << (len - i));
} else if (t[p2][0] || t[p2][1]) {
return solve(t[p1][!(t[p2][0] == 0)], t[p2][(t[p2][0] == 0)], i + 1) + (1 << (len - i));
}
} else if (t[p1][0] || t[p1][1]) {
if (t[p2][0] && t[p2][1]) {
p1 = t[p1][(t[p1][0] == 0)];
p2 = t[p2][!(t[p1][0] == 0)];
return solve(p1, p2, i + 1) + (1 << (len - i));
} else if (t[p2][0] || t[p2][1]) {
int ret = 0;
if (!((t[p1][0] == 0) == (t[p2][0] == 0))) {
ret += (1 << (len - i));
}
p1 = t[p1][(t[p1][0] == 0)];
p2 = t[p2][(t[p2][0] == 0)];
ret += solve(p1, p2, i + 1);
return ret;
}
}
}
int main() {
for (int i = 0; i <= pp; i++)
for (int j = 0; j <= 12; j++)
t[i][j] = 0;
pp = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
int num = 0;
cin >> num;
for (int j = 32; j >= 0; j--) {
tp[j] = (num & 1);
num >>= 1;
}
build(32);
}
cout << solve(0, 0, 1) << endl;
}