题目链接

算法竞赛进阶指南-57.最大异或对

在给定的 $N$ 个整数 $A_1，A_2……A_N$ 中选出两个进行 $xor$（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $A_1$～$A_N$。

输出格式

输出一个整数表示答案。

数据范围

$1 \le N \le 10^5$,
$0 \le A_i < 2^{31}$

输入样例：

3
1 2 3

输出样例：

3

Method : Trie

考虑暴力做法$O(n^2)$

int res = 0;
for (int i = 0; i < n; i ++) {
	for (int j = 0; j < i; j ++) {
		res = max(res, a[i] ^ a[j]);
	}
}

因为异或是位运算，所以以2进制的角度考虑，将所有$A_i$以2进制位拆解，从高位到低位存入(因为要选最大值，优先从高位考虑)01字典树。

在01字典树中，每次优先选择使当前高位为1的数（对于异或运算就是选与当前相反的数字)。就能把暴力做法的内层循环从$O(n)$优化到$O(31)$。

#include <vector>
#include <iostream>

using namespace std;

const int N = 1e5 + 7, M = N * 31;
const int ALPHABETS_SIZE = 2;

struct Trie {
private:
    int son[M][ALPHABETS_SIZE], idx;
public:
    // Trie() : son(ALPHABETS_SIZE, nullptr) {}
    // ~Trie() {
    //     for (auto& s : son) delete(s);
    // }
    
    void insert(int x) {
        int p = 0;
        for (int i = 30; i >= 0; i --) {
            int t = x >> i & 1;
            if (!son[p][t]) {
                son[p][t] = ++idx;
            }
            p = son[p][t];
        }
    }
    
    int query(int x) {
        int res = 0;
        int p = 0;
        for (int i = 30; i >= 0; i --) {
            int t = x >> i & 1;
            if (son[p][!t]) {
                p = son[p][!t];
                res = (res << 1) + !t;
            }
            else {
                p = son[p][t];
                res = (res << 1) + t;
            }
        }
        return res;
    }
};

int a[N];
Trie trie;

int main() {
    int n;
    cin >> n;
    for (int i = 0 ; i < n; i ++) {
        scanf("%d", &a[i]);
    }
    
    int res = 0;
    
    for (int i = 0; i < n; i ++) {
        trie.insert(a[i]);
        int t = trie.query(a[i]);
        res = max(res, a[i] ^ t);
    }
    
    cout << res << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：${O(31 * n)}$， 其中31是二进制位枚举，n是枚举a[i]。

• 空间复杂度：${O(M * ALPHABET\_SIZE)}$，M是字符串个数 * 单个字符串的最大长度。

附一个使用vector，new动态分配内存被卡MLE的。Memory Limit Exceeded

#include <vector>
#include <iostream>

using namespace std;

const int N = 1e5 + 7;
const int ALPHABETS_SIZE = 2;

struct Trie {
private:
    int cnt;
    vector<Trie*> son;
public:
    Trie() : cnt(0), son(ALPHABETS_SIZE, nullptr) {}
    ~Trie() {
        for (auto& s : son) delete(s);
    }
    
    void insert(int x) {
        Trie* p = this;
        for (int i = 30; i >= 0; i --) {
            int t = x >> i & 1;
            if (!p->son[t]) {
                p->son[t] = new Trie();
            }
            p = p->son[t];
        }
        p->cnt++;
    }
    
    int query(int x) {
        int res = 0;
        Trie*p = this;
        for (int i = 30; i >= 0; i --) {
            int t = x >> i & 1;
            if (p->son[!t]) {
                p = p->son[!t];
                res = (res << 1) + !t;
            }
            else {
                p = p->son[t];
                res = (res << 1) + t;
            }
        }
        return res;
    }
};

vector<int> a(N);
Trie trie;

int main() {
    int n;
    cin >> n;
    for (int i = 0 ; i < n; i ++) {
        scanf("%d", &a[i]);
    }
    
    int res = 0;
    
    for (int i = 0; i < n; i ++) {
        trie.insert(a[i]);
        int t = trie.query(a[i]);
        res = max(res, a[i] ^ t);
    }
    
    cout << res << endl;
    
    return 0;
}