题目描述

143.最大异或对

https://www.acwing.com/problem/content/145/

思路

遍历所有整数，对于每次遍历，从最高位搜索出和自身相异程度最高的整数，计算两者异或值
搜索中若有和当前位相异的，选取此分支并计算当前为的异或值，若无则选择另一分支并搜索下一位

代码

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

const int N=100010,M=3000010;

int a[N],son[M][2],idx;

void insert (int x)
{
    int p=0;//p指向根节点
    for(int i=30;~i;i--){//~i表示对i取反，当i=-1时取反为0，等效于i>=0
        int &s=son[p][x>>i&1];//其中s为引用等效于son[p][x>>i&1]的别名
        if(!s) s=++idx;
        p=s;//p指针下移 注意前面没有else
    }
}

int serch(int x)
{
    int res=0,p=0;
    for(int i=30; ~i;i--){
        int s=x>>i&1;
        if(son[p][!s]) res+=1<<i, p=son[p][!s];//当存在与x的第i位相反的值时，res加上此位异或结果值，并将指针p移至此节点
        else p=son[p][s];//若无，则移至另一节点
    }
    return res;
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,res=0;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i], insert(a[i]);
    for(int i=0; i<n;i++) res=max(res,serch(a[i]));

    cout <<res;
    return 0;
}