异或最大值

题目描述

给定一些数，求这些数中两个数的异或值最大的那个值

输入

多组数据。第一行为数字个数n，1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。

输出

任意两数最大异或值

样例输入

3
3
7
9

样例输出

14

解题思路

1. 首先最暴力的办法就是直接套两层循环，每一个数都跟其他数进行异或，进而找出异或最大值，这是个O(n^2) 的算法，显然是不行的。
2. 既然不能每个数都跟其他数去异或，那是不是可以尝试直接让每个数跟(n-1)个数中的某个对应的数进行异或就行？
3. 如何找到每个数所对应的另一个数？我们应该知道，异或就是将两个数按位比较，如果两个位相等则为0，不等则为1。那我们就可以将一个数转换成32位的二进制，从高位到低位，每一位都尽可能选择与本身该位不等的，做到尽量不一样才能找到最大值，这时用字典树就最好了。
4. 通过insert() 每个不同的数以二进制的形式存于字典树中，从而建立字典树。进而通过serach() 找到每个数对应的数，找出异或最大值即可。
5. 时间耗费大概是32*n，也就是O(n) 的算法。

AC代码参考

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 1e5 + 5;

struct Node {
    ll nex[2];
    Node() {nex[0] = nex[1] = -1;}
}nd[maxn * 35];

ll tp, ans;
ll mi[35], a[maxn];

void init() {
    for(int i = 0; i <= tp; i++)
        nd[i].nex[0] = nd[i].nex[1] = -1;
    tp = ans = 0;
}

void getMi() {
    mi[1] = 1;
    for(ll i = 2; i <= 32; i++)
        mi[i] = mi[i-1] * 2;
}

void insert(ll rt, ll x, ll h) {
    if(!h) return;
    ll t = x / mi[h] ? 1 : 0;
    if(nd[rt].nex[t] == -1)
        nd[rt].nex[t] = ++tp;
    insert(nd[rt].nex[t], x % mi[h], h - 1);
}

void search(ll rt, ll x, ll h, ll nowans) {
    ans = max(ans, nowans);
    if(!h) return;
    ll t = x / mi[h] ? 1 : 0;
    if(nd[rt].nex[!t] != -1)
        search(nd[rt].nex[!t], x % mi[h], h - 1, nowans + mi[h]);
    else 
        search(nd[rt].nex[t], x % mi[h], h - 1, nowans);
}

int main() {
    getMi();
    int n;
    while(cin >> n) {
        for(int i = 0; i < n; i++) {
            scanf("%lld", &a[i]);
            insert(0, a[i], 32);
        }

        for(int i = 0; i < n; i++) {
            search(0, a[i], 32, 0);
        }
        cout << ans << endl;

        //末尾初始化，节约时间
        init();
    }
    return 0;
}