【trie树】xor最大

题目大意:给定一个数集,对于每次询问,输出对应数同数集中的某个数xor的最大值。

思路:trie树+贪心

每次从高位向低位找到当前位$xor$1的节点,存在就走那个点,否则沿着当前路径向下走,走到头就是最终答案

代码↓

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

const int MAXN=1e5+5;

int n,m,x,cnt;
struct rpg{
    int vis[2];
}trie[MAXN];

void ins(int x){
    int nw=0;
    for(int i=30;i>=0;--i){
        bool fl=(1<<i)&x;
        if(!trie[nw].vis[fl]) trie[nw].vis[fl]=++cnt;
        nw=trie[nw].vis[fl];
    }return;
}

void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&x);
        ins(x);
    }return;
}

int ask(int x){
    int nw=0,sum=0;
    for(int i=30;i>=0;--i){
        bool fl=(1<<i)&x;
        if(trie[nw].vis[fl^1]){
            sum+=1<<i;
            nw=trie[nw].vis[fl^1];
        }else nw=trie[nw].vis[fl];
    }return sum;
}

void solve(){
    while(m--){
        scanf("%d",&x);
        printf("%d\n",ask(x));
    }return;
}

int main(){
    init();
    solve();
    return 0;
}