【28. 最大异或对】

概述

• 最大异或对就是在给定的数中，找到俩个数使得，这俩个数异或后的结果最大。
• 一般采用暴力法和字典树的方法。

暴力写法

#include <iostream>
#include <algorithm>
using namespace std;

const int N  = 100010;
int a[N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++)
    {
      scanf("%d", &a[i]);
    }
    int res = 0;
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < i; j ++)
        {
            res = max(res, a[i] ^ a[j]);
           
        }
    }
    cout << res << endl;
    return 0;
   
}

字典树优化

建树过程

• 从高位开始建树，因为在异或过程中（相异为1，相同为0），我们尽量满足高位最大。

程序实现

void insert(int x)
{
    int p = 0;                                        //根节点
    for (int i = 30; i >= 0; i --)                    //从最大位开始找
    {
        int u = x >> i & 1;                           //取X的第i位的二进制数是什么  x>>k&1(前面的模板)
        if (!son[p][u]) son[p][u] = ++ idx;           //如果插入中发现没有该子节点,开出这条路
        p = son[p][u];                                //指针指向下一层
    }
}

查找最大异或对结果

异或

• 俩个数都转换为二进制，如果俩个位相同异或后为0，不同异或为0。（相异为1，相同为0）

实现

• 当根节点没有数时，我们首先插入一个数
• 当再次插入第二个数时，应该先和插入的第一个数进行异或。
• 再次插入第三个数时，应该和之前插入的所有数依次异或，取得最大值。

如何查找最大呢

• 对于每一位，例如当前最高位是1，我们为了使异或后值为最大，我们就需要找最高位是0的进行异或，这样最后的结果才是最大
• 如果异或后的数是1，最好，如果不是的话，就只能是0。

代码实现

int query(int x)
{
    int p = 0, res = 0;  //用res来存取当前路径表示的数是什么
    for (int i = 30; i >= 0; i --)                   //从最大位开始找
    {
        int u = x >> i & 1;
        if (son[p][!u])                              //如果当前层有对应的不相同的数
        {
            p = son[p][!u];                          //p指针就指到不同数的地址
            res = res * 2 + !u;                      //*2代表左移一位，加上下面一位
        }                                            //例如    001 * 2 = 0010   下一位为1，
                                                     //  0010 + 1  = 00101
                                                                                 
        else
        {
            p = son[p][u];
            res = res * 2 + u;
        }
       
    }
    return res;
}

题目

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 31 * N;
int son[M][2];   //M代表节点个数(M代表一个数字串二进制可以到多长)，2代表分支只有俩个，一个是0，一个是1

int a[N];
int idx;

void insert(int x)
{
    int p = 0;                                        //根节点
    for (int i = 30; i >= 0; i --)                    //从最大位开始找
    {
        int u = x >> i & 1;                           //取X的第i位的二进制数是什么  x>>k&1(前面的模板)
        if (!son[p][u]) son[p][u] = ++ idx;           //如果插入中发现没有该子节点,开出这条路
        p = son[p][u];                                //指针指向下一层
    }
}

int query(int x)
{
    int p = 0, res = 0;  //用res来存取当前路径表示的数是什么
    for (int i = 30; i >= 0; i --)                   //从最大位开始找
    {
        int u = x >> i & 1;
        if (son[p][!u])                              //如果当前层有对应的不相同的数
        {
            p = son[p][!u];                          //p指针就指到不同数的地址
            res = res * 2 + !u;                      //*2代表左移一位，加上下面一位
        }                                            //例如    001 * 2 = 0010   下一位为1，
                                                     //  0010 + 1  = 00101
                                                                                 
        else
        {
            p = son[p][u];
            res = res * 2 + u;
        }
       
    }
    return res;
}
int main()
{
    int n;
    scanf("%d", &n); 
    for (int i = 0; i < n; i ++)  scanf("%d", &a[i]);
    
    int res = 0;
    for (int i = 0; i < n; i ++)
    {
        insert(a[i]);
        int t = query(a[i]);                         //query(a[i])查找的是a[i]值的最大与或值
        res = max(res, a[i] ^ t);
    }
    printf("%d\n", res);
    return 0;
   
}