题解：P12290 [蓝桥杯 2024 国 Java A] 基因组合

· · 题解

P12290 [蓝桥杯 2024 国 Java A] 基因组合 题解

题目链接

先考虑对于小蓝先选的情况。

不妨枚举小蓝选哪个数。设小蓝选的数为 a_i。

那么，小乔为了使结果最小，会选择与 a_i 异或结果最小的数。此时问题转化为对于一个 a_i，如何求出序列中 a_i 和其他数异或的结果的最小值。如果可以解决这个问题，那么我们可以知道小蓝选每个数时最后得到的结果，选其中最大的作为答案即可。

这个问题非常经典，可以使用 \text{01-Trie} 来解决。

先考虑求 \min_{1\le j<i} a_j\oplus a_i，那么正序遍历每个 a_i，先在 \text{01-Trie} 里查询，再将 a_i 插入字典树即可。

然后将正序遍历改为倒序遍历，即可求出 \min_{i<j\le n} a_j\oplus a_i。那么，\min_{j\neq i} a_i\oplus a_j=\min\{\min_{1\le j<i} a_j\oplus a_i,\min_{i<j\le n} a_j\oplus a_i\}。

对于所有 a_i，取 \min_{j\neq i} a_i\oplus a_j 的最大值即是第一问答案。

第二问也是类似的。将上面全部的最大、最小反过来即可。

于是容易写出代码。

#include<iostream>
using namespace std;
const int N=1e5+5,INF=0x7fffffff;
int n,tot,ans1,ans2=INF;
int a[N],trie[N*30][2],Min[N],Max[N];

void Insert(int x){
    int p=0;
    for(int i=30;i>=0;i--){
        int bit=x>>i&1;
        if(!trie[p][bit]){
            trie[p][bit]=++tot;
            trie[tot][0]=trie[tot][1]=0;
        }
        p=trie[p][bit];
    }
}

int Ask_max(int x){
    int p=0,res=0;
    for(int i=30;i>=0;i--){
        int bit=x>>i&1;
        if(!trie[p][!bit]) p=trie[p][bit];
        else p=trie[p][!bit],res+=(1<<i); 
    }
    return res;
}

int Ask_min(int x){
    int p=0,res=0;
    for(int i=30;i>=0;i--){
        int bit=x>>i&1;
        if(!trie[p][bit]) p=trie[p][!bit],res+=(1<<i);
        else p=trie[p][bit]; 
    }
    return res;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],Min[i]=INF;
    for(int i=1;i<=n;i++){
        Min[i]=min(Min[i],Ask_min(a[i]));
        Max[i]=max(Max[i],Ask_max(a[i]));
        Insert(a[i]);
    }
    trie[0][0]=trie[0][1]=0;
    for(int i=n;i;i--){
        Min[i]=min(Min[i],Ask_min(a[i]));
        Max[i]=max(Max[i],Ask_max(a[i]));
        Insert(a[i]);
    }
    for(int i=1;i<=n;i++){
        ans2=min(ans2,Max[i]);
        ans1=max(ans1,Min[i]);
    }
    cout<<ans1<<' '<<ans2;
    return 0;
}