题意：
给定n个数序列a[]，对于不同的三个数 i,j,k，求 (a[i] + a[j]) ^ a[k] 最大值
思路：
暴力 n 的三次方应该是不可行的，根据异或和性质，我们应该从高位开始，找尽量二进制位上不相同的数字的数，这样的话显然就是01字典树，
先对序列a中每一个数插入到字典树中，然后枚举 i, j ，再从字典树中删去 a[i], a[j]，查询的时候按上述方法查询，得到结果
注意题目没说a序列各个数字是不同的，因为要删除，所以还要记录每个结点访问的个数，
#include<bits/stdc++.h> using namespace std; #define out fflush(stdout) #define fast ios::sync_with_stdio(0),cin.tie(0); typedef long long ll; const int maxn = 1e5 + 7; const int maxd = 1e6 + 7; const int INF = 0x7f7f7f7f; struct trie { int root, tot, next[maxn][2], cnt[maxn]; ll val[maxn]; int newnode() { memset(next[tot], 0, sizeof next[tot]); cnt[tot] = 0; val[tot] = 0; return tot++; } void init() { tot = 0; root = newnode(); } void inser(ll x) { int p = 0; cnt[p]++; for(int i = 30; i >= 0; --i) { int id = (x>>i)&1; if(!next[p][id]) next[p][id] = newnode(); p = next[p][id]; cnt[p]++; } val[p] = x; } void delet(ll x) { int p = 0; cnt[p]--; for(int i = 30; i >= 0; --i) { int id = (x>>i)&1; p = next[p][id]; cnt[p]--; } } ll solve(ll x) { int p = 0; for(int i = 30; i >= 0; --i) { int id = (x>>i)&1; if(next[p][!id] && cnt[next[p][!id]]) { p = next[p][!id]; } else { p = next[p][id]; } } return (x ^ val[p]); } }tr; int n; ll a[1007]; int main() { int T; scanf("%d", &T); while(T--) { scanf("%d", &n); tr.init(); for(int i = 1; i <= n; ++i) { scanf("%lld", &a[i]); tr.inser(a[i]); } ll ans = 0; for(int i = 1; i < n; ++i) { tr.delet(a[i]); for(int j = i + 1; j <= n; ++j) { tr.delet(a[j]); ll t = tr.solve(a[i]+a[j]); ans = max(ans, t); // cout << i << " " << j << " = " << t << endl;; tr.inser(a[j]); } tr.inser(a[i]); } printf("%lld\n", ans); } return 0; }
