P12290

KidA · 2025-09-28 23:01:51 · 题解

看到异或，考虑 01-trie。

小乔先选的情况，相当于枚举 n 个数，对于每个数找其最大异或值的最小值。这个可以用 01-trie 轻松解决。

小蓝先选的情况，相当于枚举 n 个数，对于每个数找其最小异或值的最大值。同样可以使用 01-trie，但需要注意不能和自己异或，于是需要在之前标记独属于当前 a_i 的节点，search 时避开它们就好。

::::success[代码]

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define int long long
using namespace std;

const int N=3e6+5;
int n,tot;
int a[N],trie[N][2],vis[N],cnt[N];

void insert(int x){
    int cur=0;
    for(int i=31;i>=0;i--){
        int k=(x>>i)&1;
        if(!trie[cur][k])
            trie[cur][k]=++tot;
        cur=trie[cur][k];
        cnt[cur]++;
    }
}
int search1(int x){
    int ans=0,cur=0;
    for(int i=31;i>=0;i--){
        int k=(x>>i)&1;
        if(trie[cur][k^1])
            ans+=1<<i,cur=trie[cur][k^1];
        else
            cur=trie[cur][k];
    }
    return ans;
}
int search2(int x){
    int ans=0,cur=0;
    for(int i=31;i>=0;i--){
        int k=(x>>i)&1;
        if(trie[cur][k]&&!vis[trie[cur][k]])
            cur=trie[cur][k];
        else
            ans+=1<<i,cur=trie[cur][k^1];
    }
    return ans;
}
void mark(int x,int f){
    int cur=0;
    for(int i=31;i>=0;i--){
        int k=(x>>i)&1;
        cur=trie[cur][k];
        if(cnt[cur]==1)
            vis[cur]=f;
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],insert(a[i]);
    int ans2=1e18;
    for(int i=1;i<=n;i++)
        ans2=min(ans2,search1(a[i]));
    int ans1=-1e18;
    for(int i=1;i<=n;i++)
        mark(a[i],1),ans1=max(ans1,search2(a[i])),mark(a[i],0);
    cout<<ans1<<' '<<ans2;
    return 0;
}

::::