目录

• Description
• State
• Input
• Output
• Solution
• Code

Description

? 有 n 个数，求 $ max((a[i] + a[j]) ⊕ a[k]) $ ，其中 \(i, j, k\) 互不相同

State

? 测试样例 $ 1<=T<=1000 $
? $ 3<=n<=1000 $
? $ 0<=a[i]<=1e9 $

Input

2
3
1 2 3
3
100 200 300

Output

6
400

Solution

题目 n 并不是很大，所以推测算法复杂度为 \(O(n^2logn)\)
其中枚举 \(a[i] + a[j]\) 复杂度为 \(O(n^2)\)
再找一个数 x ，使得 \((a[i] + a[j]) ⊕ x\) 最大，利用 01Trie，复杂度为 O(logA)

Code

   const int N = 4e5 + 5;

    ll n, m, _;
    int i, j, k;
    ll a[N];
    int ch[N * 30][2], sz[N * 30];
    int tot = 0;

void ins(int x)
{
    int rt = 0;
    for(int i = 30; ~i; i --){
        int id = (x >> i) & 1;
        if(ch[rt][id] == 0){
            ch[rt][id] = ++ tot;
        }
        rt = ch[rt][id];
        sz[rt] ++;
    }
    return void();
}

void update(int x, int c)
{
    int rt = 0;
    for(int i = 30; ~i; i --){
        int id = (x >> i) & 1;
        rt = ch[rt][id];
        sz[rt] += c;
    }
    return void();
}

ll query(ll x)
{
    int rt = 0;
    ll ans = 0;
    for(int i = 30; ~i; i --){
        int id = (x >> i) & 1;
        if(sz[ch[rt][!id]]){
            rt = ch[rt][!id];
            ans |= (1 << i);
        }
        else{
            rt = ch[rt][id];
        }
    }
    return ans;
}

void clear()
{
    for(int i = 0; i <= tot; i ++){
        ch[i][0] = ch[i][1] = 0;
        sz[i] = 0;
    }
    tot = 0;
    return void();
}

signed main()
{
    //IOS;
    rush(){
        sd(n);
        rep(i, 1, n){
            sd(a[i]);
            ins(a[i]);
        }
        ll maxx = 0;
        rep(i, 1, n){
            rep(j, i + 1, n){
                update(a[i], -1);
                update(a[j], -1);
                maxx = max(maxx, query(a[i] + a[j]));
                update(a[i], 1);
                update(a[j], 1);
            }
        }
        pd(maxx);
        clear();
    }
    return 0;
}