Find MaxXorSum NBUT - 1597（字典樹）

點選打開連結

Given n non-negative integers, you need to find two integers a and b that a xor b is maximum. xor is exclusive-or.

Input

Input starts with an integer T(T <= 10) denoting the number of tests. 

For each test case, the first line contains an integer n(n <= 100000), the next line contains a1, a2, a3, ......, an(0 <= ai <= 1000000000);

Output

For each test case, print you answer.

Sample Input

2
4
1 2 3 4
3
7 12 5      

Sample Output

7
11      

Hint

無      

題意：給出n個整數，要求n個數裡面找出兩個數，那兩個數的亦或值最大。

一開始寫了一個自認為很有道理的貪心，找出最大和次大的兩個值，最大的亦或值一定是這兩個數和其他數的亦或，天真的以為最大和次大的兩個數的二進制長度一定最長，wa了兩發之後被學長一個樣例就推翻了（太丢臉了2333）

下面講一下正确的解法：

最大亦或值，我們首先想到的是二進制，是以要把n個數變成二進制存進字典樹裡面，然後在樹上dp就可以了

#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<set>
#include<stdlib.h>
#include<queue>
#include<vector>
#include<math.h>
using namespace std;
typedef long long ll;
int tot;
struct Trie{
    int nxt[2];
    void init(){
        memset(nxt , -1 , sizeof(nxt));
    }
}L[2000000];//字典樹
void add(int x){
    int p = 0;
    for(int i = 30 ; i >= 0 ;){
        bool v = x&(1<<i);//數字的二進制目前位置為0還是1
        if(L[p].nxt[v] == -1){
            L[tot].init() ;
            L[p].nxt[v] = tot++;
        }
        p = L[p].nxt[v];
        i--;
    }
}
int query(int x){//查詢
    int p = 0;
    int ans = 0;
    for(int i = 30 ; i >=0 ; ){
        bool v = x&(1<<i);
        if(L[p].nxt[!v] == -1){
            p = L[p].nxt[v];
        }
        else{
            p = L[p].nxt[!v];
            ans += (1<<i) ;
            //cout<<ans<<endl;
        }
        i--;
    }
    return ans ;
}
int aa[100005];
int main()
{
    int t , n;
    scanf("%d",&t);
    while(t--){
        tot = 1 ;
        L[0].init();
        scanf("%d",&n);
        for(int i = 0 ; i < n ; i ++){
            scanf("%d",&aa[i]);
            add(aa[i]);
        }
        int ans = 0;
        for(int i = 0 ; i < n ; i ++)
            ans = max(ans , query(aa[i]));
       printf("%d\n",ans);
    }
    return 0;
}