AcWing：143. 最大异或对（01字典树 + 位运算 + 异或性质）

2022-09-29 09:23:19

在给定的N个整数

输入格式

第一行输入一个整数N。

第二行输入N个整数

输出格式

输出一个整数表示答案。

数据范围

输入样例：

3
1 2 3

输出样例：

算法：01字典树 + 位运算 + 异或性质

题解：首先我们并看不出来这个题目需要用到字典树，但是，我们可以发现数据的范围只有31位，那么我们就可以同过这个点来建立关于位数的字典树。首先，我们把每个数的二进制看作一个字符串，然后开始建树...查询的话，就是每次匹配异或1之后的数（假如是1，你就找0，相反，则找1），如果每次找到的是异或之后的数，你就把当前位赋1。

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 1e5+7;

int tree[maxn * 30][2];
int tot;

void insert(int x) {
    int root = 0;
    for(int i = 30; i >= 0; i--) {
        int idx = (x >> i) & 1;     //获取每位的值
        if(tree[root][idx] == 0) {
            tree[root][idx] = ++tot;
        }
        root = tree[root][idx];
    }
}

int search(int x) {
    int ans = 0;
    int root = 0;
    for(int i = 30; i >= 0; i--) {
        int idx = (x >> i) & 1;
        if(tree[root][1 ^ idx] != 0) {      
            ans |= (1 << i);    //如果当前位不同，就把当前位赋1
            root = tree[root][1 ^ idx];
        } else {
            root = tree[root][idx];
        }
    }
    return ans;
}

int main() {
    int n;
    scanf("%d", &n);
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        insert(x);
        ans = max(ans, search(x));
    }
    printf("%d\n", ans);
    return 0;
}