143. 最大异或对(字典树 + 位运算)

刺骨的言语ヽ痛彻心扉 2021-12-05 21:43 271阅读 0赞

### 题目描述： ###

在给定的N个整数A1，A2……AN

中选出两个进行xor（异或）运算，得到的结果最大是多少？  
输入格式

第一行输入一个整数N。

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

。  
输出格式

输出一个整数表示答案。  
数据范围

1≤N≤105  
,  
0≤Ai<231

输入样例：

3  
1 2 3

输出样例：

##### 分析： #####

这个题，我们可以使用字典树。我们把一个数的二进制串看成一个字符串。建成字典树之后，我们对每一个数进行查询。查询与他的二进制串相反的串。

注意：因为本题 我对位运算的操作模糊了。导致wa了好久。  
int k = (x >> i) & 1 ; 将第i位取出应该这样写。我一开始写成了 int k = x & (1 << i )。这是错误写法。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    typedef struct Node
    {
        int val;
        int end_num;
        int child[2];
        Node()
        {
            val = 0; end_num = 0; child[0] = 0;
            child[1] = 0;
        }
    }Node;
    
    Node node[1000101];
    int node_num,N;
    int a[100100];
    int maxx = 0;
    
    void Creat_Tree(int x)
    {
       int id = 0;
       for(int i = 31; i >= 0; i --)
       {
           int k = (x >> i)   & 1 ;
           if(node[id].child[k] != 0)
           {
               id = node[id].child[k];
           }
           else
           {
               node[id].child[k] = ++ node_num;
               id = node[id].child[k];
           }
       }
       node[id].end_num ++;
    }
    
    void Serch(int x)
    {
        int id = 0;
        int val = 0;
        for(int i = 31; i >= 0; i --)
        {
           int k = !((x >> i)   & 1);
    
            if(node[id].child[k] != 0)
            {
                id = node[id].child[k];
                if(k == 1)
                 val = val | (1 << i);
            }
            else
            {
                id = node[id].child[!k];
                if((!k) == 1)
                    val = val | (1 << i);
            }
            //printf("x = %d k = %d\n",x,k);
        }
        //printf("x = %d val = %d\n",x,val);
        maxx = max(maxx,val ^ x);
    }
    
    int main()
    {
        scanf("%d",&N);
        for(int i = 1; i <= N; i ++)
        {
            scanf("%d",&a[i]);
            Creat_Tree(a[i]);
        }
        for(int i = 1; i <= N; i ++)
        {
            Serch(a[i]);
        }
        printf("%d\n",maxx);
    }