AcWing-143-最大异或对

问题

在给定的 NN 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 N。

第二行输入 N 个整数 A1-AN。

输出格式

输出一个整数表示答案。

数据范围

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

输入样例：

3
1 2 3

输出样例：

3

思路

字典树，将A数组的31位二进制插入字典树，在搜索的时候，尽量走与当前位相反的位（如果该位在字典树中存在路径的话），这样到最后一位的时候，得到的路径就是搜索的数字A[j]，与其他数异或后最大的数A[i]。

题解

题解一

• 利用bitset库，时间开销较大

#include<iostream>
#include<cstdio>
#include<bitset>
#include<string>

using namespace std;
const int MAX = 1e5 + 5;
const int SIZE = 1e7;
int trie[SIZE][2], cnt = 1, str_end[SIZE];
int a[MAX], n;

void insert(string str, int num) {
    int len = str.length(), p = 1;
    for (int k = 0; k < len; ++k) {
        int ch = str[k] - '0';
        if (trie[p][ch] == 0) trie[p][ch] = ++cnt;
        p = trie[p][ch];
    }
    str_end[p] = num;
}

int search(string str) {
    int len = str.length(), p = 1;
    for (int k = 0; k < len; ++k) {
        int ch = str[k] - '0';
        if (trie[p][ch ^ 1] != 0) ch ^= 1;
        p = trie[p][ch];
    }

    return str_end[p];
}

int main() {
    cin >> n;
    int max_val = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        bitset<32> str(a[i]);
        insert(str.to_string(), a[i]);
        max_val = max(max_val, a[i] ^ search(str.to_string()));
    }

    cout << max_val << endl;

    return 0;
}

题解二

• 利用位运算，时间复杂度降低

#include<iostream>
#include<cstdio>

using namespace std;
const int MAX = 1e5 + 5;
const int SIZE = 1e7;
int trie[SIZE][2], cnt = 1, a, n;

void insert(int num) {
    int p = 1;
    for (int k = 30; k >= 0; --k) {
        int ch = num >> k & 1;
        if (trie[p][ch] == 0) trie[p][ch] = ++cnt;
        p = trie[p][ch];
    }
}

int search(int num) {
    int p = 1, ans = 0;
    for (int k = 30; k >= 0; --k) {
        int ch = num >> k & 1;
        if (trie[p][ch ^ 1] != 0) {
            ch ^= 1;
            ans |= (1 << k);    //不同路，则该位的最终异或结果一定为１
        }
        p = trie[p][ch];
    }

    return ans;
}

int main() {
    cin >> n;
    int max_val = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a);
        insert(a);
        max_val = max(max_val, search(a));
    }

    cout << max_val << endl;

    return 0;
}