当前位置：首页 > article >正文

最大异或对（每周一类）

article 2024/10/8 22:31:59

今天我们来看这个最大异或类这道题最大异或对

1.首先，我们先来了解一下异或是什么，之后还要讲一下同或。

众所周知，数字在计算机中是由二进制来表示的，比如十进制的7，用二进制表示就是 111，十进制的3，用二进制表示就是011,。形象一点表示如下图：

3与7进行异或操作就是将二进制相同的地方变成0，不同的地方变成1，在示例中，就变成了4。

简单理解，就异（不一样的地方）变成1,。

同或就是相反，同（相同的地方）变成1，不相同的地方变成0。

好，在理解了基础概念再看这道题，就是我们用暴力的方法，就是两重循环，一个个来做异或，比较他们的大小，最后找出最大的异或对。在c++中，异或的运算符号是^，比如要计算a异或b，就写 a ^ b 就好。

在理解了题意之后，我们来做一下代码（暴力）：

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010;

int main(){
    int n;
    cin >> n;
    int a[N];
    for(int i = 0; i < n ; i ++ ){
        scanf("%d",&a[i]);
    }
    int res = -1;
    for(int i = 0; i < n ; i ++ ){
        for(int j = i + 1; j < n; j ++ ){
            int x = a[i]^a[j];
            res = max(res,x);
        }
    }
    printf("%d\n",res);
    return 0;
}

时间复杂度是O（n^2）有点太大了，我们要进行优化，方法就是 Trie 树，由于对于每一个数，我们总有办法找到最好的，能匹配它的数，使得他们的异或值最大，如下图，我们找和十进制的 5 匹配的数字，5变成二进制是101，我们要找的就是二进制是010的数字，就是2。

按照这个思路，我们在存进去一个数的时候，就可以存储Trie树，当查找最大值的时候，我们就可以对刚刚暴力循环的第二层进行优化之后的查找，效率会更高。具体代码如下：

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010, M = 3100010;

int n;
int a[N], son[M][2], idx;

void insert(int x){
    int p = 0;
    for(int i = 30; i >=0; i -- ){
        int &s = son[p][x >> i & 1];
        if(!s) s = ++idx;
        p = s;
    }
}
int search(int x){
    int p = 0, res = 0;
    for(int i = 30; i >= 0; i --)
    {
        int s = x >> i & 1;
        if(son[p][!s]){
            res += 1 << i;
            p = son[p][!s];
        }
        else p = son[p][s];
    }
    return res;
}

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

和上一节一样，我们存储的时候要定义索引 p ，刚开始是 0 ，随着 idx 的增加，而递增，用于判断不同的数字变成的二进制串，如果输入的串存在，那么就继续；如果不存在，就创建。在查找的时候，如果查找的串存在，就继续，如果不存在，就输出相反字符，比如我们对 101 的期望是 010，但如果没有 010 ，只有 011，我们就找 011串。

其中对于每一个数字的处理，我们是从高位到低位进行处理，我们从31到0位进行存入或者查找。

这节课可以参照着上节课一起看，将Trie树的模版掌握并会自己写，就可以迎刃而解

查看全文

http://www.kler.cn/news/338981.html