trie变形 存二进制位

题目 最大异或对

思路分析

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=100010,M=3100010;//一个int最多31位 所以结点最大为31*N

int a[N],son[M][2];//孩子顶多两个 0或1

int idx;

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 search(int x)

{

    int p=0,res=0;

    for(int i=30;i>=0;i--)

    {

        int u=x>>i&1;

        if(son[p][!u])//理想情况存在

        {

             res=res*2+1;//左移一位且该位为1

             p=son[p][!u];

        }

        else

        {

            res=res*2+0;//左移一位且该位为0

            p=son[p][u];

        }

    }

    return res;

}

int main()

{

    int n;

    cin>>n;

    for(int i=0;i<n;i++)

    {

        scanf("%d",&a[i]);

        //预想是在插入前先查询 但是为了减少边界情况的判断（第一次没有）

        //就先插入 再查询 其实不会影响结果 自己和自己异或的结果是0

        insert(a[i]);

    }

    int res=0;

    for(int i=0;i<n;i++)

        res=max(res,search(a[i]));//结果用res维护 找到更大的再更新

    cout<<res<<endl;

    return 0;

}

同类题型

视频讲解

⬅️ trie树 🏠 00-听课板子 ➡️ 并查集