自动搬运

查看原文

来自洛谷，原作者为

	hjhAKIOI “希望大家永远忘了我。“

搬运于2025-08-24 23:14:23，当前版本为作者最后更新于2025-05-04 21:12:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}