Tire树练习题

T1 「一本通 2.3 例 2」The XOR Largest Pair

在给定的 \(N\) 个整数\(A_1,A_2,...A_N\)中选出两个进行异或运算，得到的结果最大是多少？

数据范围

对于 100%的数据，\(1 \leq N \leq 10^5,0 \leq A_i \leq 2^{31}\)

1.朴素算法并用二分查去匹配二进制下每个数最高位的0还是能卡过的

2.结合异或的运算规则，怎样才能使两个数的异或和尽量大呢？答案是尽量让二进制下每一位都不同，如果对于每个数x，能直接找到某一位和它不同的数，那就可以贪心选取二进制下尽量不一样的数了。那怎么找呢？

3.结合数据范围发现每个数写成二进制最多才31位，每一位01两个状态。所以对每个数的二进制建trie树（深度越浅代表的二进制位越高，树的size最大为\(N*31\) ）,对于每个数，在trie树上每走一步就贪心地选当前位和它不一样的数

为什么这样贪一定使对的呢？假设当前数的第k位是0，trie树上的第k位存在1，那要么选这个1，则对结果有\(2^k\)的贡献;要么不选1选0，则后面的数位总共对结果最多有\(2^k-1\)的贡献，故第k位选相反数一定使更优的。算法正确性得证。

\(Code:\)

#include<bits/stdc++.h>
using namespace std; 
#define F(i,l,r) for(int i=l;i<=r;++i) 
#define G(i,r,l) for(int i=r;i>=l;--i) 
const int N=1e5+5,M=20;
int n,num=0,mx=-1,z,a[N*M],ch[N*M][2],val[N*M];
inline void insert(int x){
	int p=0;
	G(i,30,0){
		z=x&(1<<i)?1:0;
		if(!ch[p][z]) ch[p][z]=++num;
		p=ch[p][z];
	} val[p]=x;
}
inline void qry(int x){
	int p=0;
	G(i,30,0){
		z=x&(1<<i)?1:0;
		if(ch[p][1^z]) p=ch[p][1^z];
		else if(ch[p][z]) p=ch[p][z];
	}
	mx=max(mx,x^val[p]);
}
int main(){
	scanf("%d",&n);
	F(i,1,n) scanf("%d",&a[i]),insert(a[i]);
	F(i,1,n) qry(a[i]);
	printf("%d",mx);
	return 0;
}