题目描述

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

输入格式
第一行输入一个整数N。

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

输出格式
输出一个整数表示答案。

数据范围
1≤N≤105,
0≤Ai<231
输入样例：
3
1 2 3
输出样例：
3

思路

（基于贪心的思想）
异或是一种不进位加法（基于二进制的方法下）。0 xor 1=1，本身异或本身结果为0；
那么就可以想到一种贪心的方法是：一个数和一个与自己的每一个二进制位都不相同的数字异或，这样子的结果一定最优。
如果说是纯暴力的写for循环，这样子的话，应该是O(n^2)的做法：
第一层枚举每一个数字；
第二层在枚举每一个数字，与之异或。
所以说：应该要优化成O(n)或者是O（nlogn）的。
此时就可以想到字典树（trie树）：
把每一个数字的二进制位保留到树上；
这样子的话，再每遍历一遍整个数字，就是O(nlogn)的复杂度。
为什么说是基于贪心的呢？？
首先是按位异或，给每一位都找到一个可以异或出来最大的数字；
其次是按最高位异或，这样子的话，找到一个可以异或的数字就是使得异或的最大值增加最多的。

code

#include<bits/stdc++.h>
using namespace std;

const int nn=1e5+10;

int n;
int tri[32*nn][10],tot=1;
int a[nn];
int maxx=0;

void insert(int str)
{
    int p=1;
    for(int k=31;k>=0;--k)
    {
        int ch=(str>>k)&1;
        if(!tri[p][ch]) tri[p][ch]=++tot;
        p=tri[p][ch];
    }
}

int search(int x)
{
    int p=1;
    int ans=0;
    for(int k=31;k>=0;--k)
    {
        int ch=(x>>k)&1;
        if(tri[p][ch^1])
        {
            p=tri[p][ch^1];
            ans|=1<<k;
        }
        else p=tri[p][ch];
    }
    return ans;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)   cin>>a[i],insert(a[i]);
    for(int i=1;i<=n;++i)   maxx=max(maxx,search(a[i]));
    cout<<maxx<<endl;
    return 0;
}