AcWing | 最大异或对

「爱情、让人受尽委屈。」 2022-12-19 11:47 155阅读 0赞

**题目内容：**

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

**输入格式**

> 第一行输入一个整数N。
> 
> 第二行输入N个整数A1～AN。

**输出格式**

> 输出一个整数表示答案。

**数据范围**

> 1≤N≤105, 0≤Ai<231

**输入样例：**

3
    1 2 3

**输出样例：**

--------------------

**思路：**

*  这题是Trie树的变题（[看Trie树例题][Trie]）
 *  首先把所有数字以二进制的方式存储到Trie树里面；
 *  然后从根节点（最高位）开始往下走，遍历当前节点的时候，看看当前节点的异或值能不能走，如果能走就继续往下，不能的话只能按当前路走。
 *  然后重复上一个步骤，一边遍历一边记录最大值，当全部遍历结束的时候最大异或值也就出来了。
 *  `u=x>>i&1`是让x右移i位再“与”上1，用来查看x二进制从最低位开始数第i位的值是0还是1。
 *  举个例子就懂了：

<table> 
 <thead> 
  <tr> 
   <th>原数组</th> 
   <th>二进制表示</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>001</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>010</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>011</td> 
  </tr> 
 </tbody> 
</table>

*  首先我们把\[1,2,3\]以二进制形式存到Trie里面
 *  然后比如我们要求1异或的最大值的话，从最高位开始看
    
     *  我们希望最好的结果是“110”这样异或上“001”的话能最大是“111”了，但是我们查看Trie树，发现最高位只能走0，；
     *  然后第二位可以是1，第三位可以是0，这样就得出了1在数组内异或2后可以得到最大异或值3
     *  然后再用一个循环来取其他值的最大异或值
     *  最后就能得到答案了

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70_pic_center]

**时间复杂度分析：** 建完Trie树以后每个数查询一次，所以时间复杂度是O（n）

**完整代码：**

#include<iostream>
    #include<algorithm>
    using namespace std;
    const int N=100010,M=3000000;
    int n;
    int son[M][2],idx;
    int a[N];
    
    void insert(int x){ 
        int p=0;
        for(int i=30;i>=0;i--){ 
            int u=x>>i &1;
            if(!son[p][u])son[p][u]=++idx;//如果该节点不存在，就创建它
            p=son[p][u];//往下走
        }
    }
    int query(int x){ 
        int res=0,p=0;
        for(int i=30;i>=0;i--){ 
            int u=x>>i&1;//x右移i位&1，查看x的第i位是0还是1
            if(son[p][!u]){ 
                //如果当前子树中，存在第 i位和 x 的第 i 位不同的数，
                //说明答案的第 i 位可以变成1，就把 res 的第 i 位二进制位变成1。
                res+=1<<i;
                p=son[p][!u];
            }else p=son[p][u];//不然只能从当前分支走
        }
        return res;
    }
    int main(){ 
        cin>>n;
        for(int i=0;i<n;i++){ 
            cin>>a[i];
            insert(a[i]);
        }
        int res=0;
        for(int i=0;i<n;i++){ 
            res=max(res,query(a[i]));
        }
        cout<<res<<endl;
        return 0;
    }

[Trie]: https://blog.csdn.net/qq_43145926/article/details/109522172
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/ecb848a4f434429daea436d41fdefb7d.png