点击打开链接
题意:t组数据n个数,t,n<=1e3 求max((si+sj) XoR sk) i,j,k为三个不同的下标
//先在n个数以二进制形式插入到Trie中,枚举i,j后,暂时在Trie中删除i,j 然后在Trie找到最大的异或值,在插入i,j; O(n^2*32*5)
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e3+20; ll ch[32*N][2],v[32*N],sz; ll a[N]; int num[32*N];//num[u] 结点u是多少个二进制的前缀 void init() { memset(ch[0],0,sizeof(ch[0])); memset(v,0,sizeof(v)); memset(num,0,sizeof(num)); sz=1; } void insert(ll x) { int u=0; for(int i=32;i>=0;i--) { int c=(x>>i)&1; if(!ch[u][c]) { memset(ch[sz],0,sizeof(ch[sz])); ch[u][c]=sz++; } u=ch[u][c]; num[u]++; } v[u]=x; } void update(ll x,int d) { int u=0; for(int i=32;i>=0;i--) { int c=(x>>i)&1; u=ch[u][c]; num[u]+=d;//删一次'边'. } } ll query(ll x) { int u=0; for(int i=32;i>=0;i--) { int c=(x>>i)&1; //优先走到异或为1的点 && 相反点此时还存在 if(ch[u][c^1]&&num[ch[u][c^1]]) u=ch[u][c^1]; else u=ch[u][c]; } return x^v[u]; } int main() { int t; cin>>t; while(t--) { ll ans=0; init(); int n; cin>>n; for(int i=1;i<=n;i++) { scanf("%I64d",&a[i]); insert(a[i]); } for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { update(a[i],-1); update(a[j],-1); ans=max(ans,query(a[i]+a[j])); update(a[i],1); update(a[j],1); } } cout<<ans<<endl; } return 0; }