标准的 01 Trie 。

#include <bits/stdc++.h>

using namespace std;

int n, a[1000005], trie[10000005][2], p = 1, ans;

void insert(int u, int x, int b) {
    if (!x) return;
    if (!trie[u][(x >> b) & 1]) trie[u][(x >> b) & 1] = ++p;
    insert(trie[u][(x >> b) & 1], x - (((x >> b) & 1) << b), b - 1);
}

int search(int u, int x) {
    int res = 0, t = u;
    for (int i = 30; i >= 0; i--) {
        if (!t) break;
        if (trie[t][!((x >> i) & 1)]) {
            res += 1 << i;
            t = trie[t][!((x >> i) & 1)];
        } else {
            t = trie[t][(x >> i) & 1];
        }
    }
    return res;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
        insert(1, a[i], 30);
    }
    for (int i = 0; i < n; i++) {
        ans = max(ans, search(1, a[i]));
    }
    printf("%d\n", ans);
    return 0;
}

Personal Homepage | Blog | OI Blog

楼上使用的是递归版的01Trie插入。 我用的循环的方式:

#include <bits/stdc++.h>
#include <cstdlib>

using namespace std;

const int N=31000010;
int son[N][2];
int cnt[N];
int idx;

int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
    	ch=getchar();
    	if(ch=='-')f=-1;
    }
    while('0'<=ch&&ch<='9')
    {
    	x=x*10+ch-'0';
    	ch=getchar();
    }
    return x*f;
}

void insert(int x)
{
    int p=0;
    for(int i=31;i>=0;i--)
    {
        int u=x>>i&1;
        if(!son[p][u])son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}

int n;
int res=0x80808080;

int findxor(int x)
{
    int p=0,res=0;
    for(int i=31;i>=0;i--)
    {
        int u=x>>i&1;
        if(son[p][!u])p=son[p][!u],res+=1<<i;
        else p=son[p][u];
    }
    return res;
}

int a[N];

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        insert(a[i]);
    }
    for(int i=1;i<=n;i++)res=max(res,findxor(a[i]));
    printf("%d\n",res);
    return 0;
}

#include <iostream>

using namespace std;
int rec[10000005][2];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int amount, n;
    int cnt = 0;
    cin >> amount;

    int result = 0;
    for (int i = 0; i < amount; i++) {
        cin >> n;
        int insert_p = 0;
        int search_p = 0;
        int val = 0;
        int bits = 30;
        while (bits >= 0) {
            int head = n >> bits & 1;
            if (rec[insert_p][head] == 0) {
                rec[insert_p][head] = ++cnt;
            }
            insert_p = rec[insert_p][head];

            if (rec[search_p][1 - head] != 0) {
                search_p = rec[search_p][1 - head];
                val += 1 << bits;
            } else {
                search_p = rec[search_p][head];
            }
            bits--;
        }
        if (val > result) { result = val; }
    }

    cout << result;
    return 0;
}

insert 和 search 可以一个循环一起完成

我不理解为什么有人说一定要快读

#include<vector>
#include<cstdio>
#include<limits>


class Trie
{
	public:
		typedef std::size_t NodeId;
		static constexpr NodeId NIL=static_cast<NodeId>(-1);
	private:
		struct TrieNode
		{
			NodeId zero;
			NodeId one;
			inline constexpr TrieNode():zero(NIL),one(NIL){}
		};
		
		std::vector<TrieNode> child;
		
	public:
		inline Trie():child(1ull){}
		
		bool hasChild(NodeId parent,bool childValue){
			if(childValue && child.at(parent).one==NIL) return false;
			else if(!childValue && child.at(parent).zero==NIL) return false;
			else return true;
		}
		
		NodeId getChild(NodeId parent,bool childValue){
			if(childValue) return child.at(parent).one;
			else return child.at(parent).zero;
		}
		
		void insertNode(NodeId parent,bool childValue){
			if(childValue && child.at(parent).one==NIL){
				child.at(parent).one=child.size();
				child.emplace_back();
			}else if(!childValue && child.at(parent).zero==NIL){
				child.at(parent).zero=child.size();
				child.emplace_back();
			}
		}
		
		static inline constexpr NodeId getRootId(){
			return 0ull;
		}
		
		void insertNumber(int x){
			int u=this->getRootId();
			for(int i=31;i>=0;i--){
				bool bit=static_cast<bool>((x>>i)&1);
				this->insertNode(u,bit);
				u=this->getChild(u,bit);
			}
		}
		
		int findXor(int x){
			int u=this->getRootId(),res=0;
			for(int i=31;i>=0;i--){
				if(u==NIL) u=0;
				bool bit=static_cast<bool>((x>>i)&1);
				if(this->hasChild(u,!bit)){
					u=this->getChild(u,!bit);
					res+=1<<i;
				}else{
					u=this->getChild(u,bit);
				}
			}
			return res;
		}
};


int main(){
	int n,ans=std::numeric_limits<int>::min();
	scanf("%d",&n);
	int *a=new int[n];
	Trie* tr=new Trie;
	for(int i=0;i<n;i++){
		scanf("%d",a+i);
		tr->insertNumber(a[i]);
	}
	for(int i=0;i<n;i++){
		ans=std::max(ans,tr->findXor(a[i]));
	}
	printf("%d",ans);
	delete tr;
	delete []a;
	return 0;
}

#include <bits/stdc++.h>
#include <cstdlib>

using namespace std;

const int N=31000010;
int son[N][2];
int cnt[N];
int idx;

int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
ch=getchar();
if(ch=='-')f=-1;
}
while('0'<=ch&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}

void insert(int x)
{
int p=0;
for(int i=31;i>=0;i--)
{
int u=x>>i&1;
if(!son[p][u])son[p][u]=++idx;
p=son[p][u];
}
cnt[p]++;
}

int n;
int res=0x80808080;

int findxor(int x)
{
int p=0,res=0;
for(int i=31;i>=0;i--)
{
int u=x>>i&1;
if(son[p][!u])p=son[p][!u],res+=1<<i;
else p=son[p][u];
}
return res;
}

int a[N];

int main()
{
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
insert(a[i]);
}
for(int i=1;i<=n;i++)res=max(res,findxor(a[i]));
printf("%d\n",res);
return 0;
}

基础的 $\tt 01Trie