题目描述

1. 要求最大的异或对，暴力解法是将所有的数依次组对求异或，这样的对有n*(n-1)/2个，因此要做N平方级别次数的异或算，显然会超时。
2. 考虑到求最大异或值得特点：
   A.从最高位s=x>>i&1开始算，优先找!s(即0优先找1,1优先找0，这样才能异或为1)，若没有才去表示值为s的节点。而二进制中非0即1，因此很多查找过程都是重复的。
   B.在上述计算中，需将数化成二进制数，即01串，用trie树存可以节省很多重复节点，既节省空间，又能提高查找效率

C++ 代码

#include<iostream>
using namespace std;
const int N=100010,M=3000000;

//son数组用来存trie树，a数组用来读入所用数据，idx表示当前已用到son中第idx个节点，res存最大异或值
int son[M][2],a[N],idx,res;

//trie树的节点创建函数
void insert(int x)
{
    //从根节点开始
    int p=0;

    for(int i=30;~i;i--)   //i从30开始是因为要从数的高位开始取（位数从0开始计数）
    {
        //这里的&是C++中“传引用”用法，即后面改变s的值时，也会改变son中节点的值
        //x>>i&1就是看x对应二进制数的第i位是1还是0
        int &s=son[p][x>>i&1];

        //若该节点还没有被插入过，则插入，新节点的值为下一个节点的位置
        if(!s)
            s=++idx;

        p=s;
    }
}

//查询每个数据在所有数据中的最大异或值
int query(int x)
{
    //res为该函数中存res的值，全局变量res在该函数中则不起作用
    int res=0,p=0;
    for(int i=30;~i;i--)
    {
        int s=x>>i&1;
        if(son[p][!s])              //如果该节点存有!s，则res值加上该值，否则只能“前往”s的子节点
        {
            res+=1<<i;
            p=son[p][!s];
        }
        else    p=son[p][s];
    }
    return res;
}
int main()
{
    int n;
    cin>>n;

    //读入数据的同时建树
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        insert(a[i]);
    }

    //依次求最大异或值
    for(int i=1;i<=n;i++)
    {
        res=max(res,query(a[i]));
    }
    cout<<res;
    return 0;
}

ps

这棵trie树没有加标记是因为每个二进制串我们都看成31位的，不足的补0，因此用~i来判断该串是否走到尽头