〔ACwing 143〕最大异或对

发表于 更新于
引用某大佬的话:"好题!"
$ 🔄原题面🔄 $

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

输入格式

第一行输入一个整数 \(N\)

第二行输入 \(N\) 个整数 \(A_1,A_2,A_……A_N\)

输出格式

输出一个整数表示答案。

数据范围

\(1\) ≤ \(N\) ≤ \(10^5\) ,
\(0\) ≤ \(A_i\) < \(2^{21}\)

输入样例：

3
1 2 3

输出样例：

3

  正文开始,这题一看,正解无从下手,第一时间脑子里是暴力枚举。 (完了,蒟蒻实锤了)

  于是看了算法标签和题解

  1. 让我们先看关键字:"异或"。 Q: 那么异或的性质是什么? A: 把两个数\(_{\left(10\right)}\)转化为\(2\)进制的,然后按位(一位一位的)去比较,不相同的位为1,否则为0

  2. 有了合并的法则,而且题目中说要最大,我们就能理所当然的想到贪心:让两个尽可能的大、按位尽可能不想同的进行异或

  3. 那么该怎么做能? 我们应该优先让 较高位不同 举个10进制的例子就号明白了,1999和999后三位同样是9但是前一位才是再大小上起决定作用的。二进制也一样的

如图(我知道丑爆了,别骂了QwQ): 示意图1

  那么我们要优先遍历靠前的,就应该找一个数据结构把他存起来,还能高效比较各个位。 理所当然的,那就是字典树(tire)

 后面的比较就按思想来就行了

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
const int maxn=100010;
int in[maxn];//记录输入
int n,cnt,ans;//cnt:处理tire的中间遍历
int trie[maxn*32][2];//tire本体,A<2^31,N<10^5

int work(int s);
void insert(int s);

int main() {
	// freopen("in.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&in[i]);
		insert(in[i]);
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,work(in[i]));//没有让我们说那两个异或最大只问了结果
	}
	printf("%d",ans);
	//over 
    return 0;
}
void insert(int s){
	int root=0;
	for(int i=31;i>=0;--i){//从高到低
		int value=(s>>i)&1;//位运算,取位值
		if (!trie[root][value]){
			trie[root][value]=++cnt;
		}
		root=trie[root][value];
	}
	return ;
}
int work(int s){
	int root=0,maxn=0;
	for(int i=31;i>=0;--i){
		int value=(s>>i)&1;
		if (trie[root][!value]){
			maxn=(maxn<<1)|1;
			root=trie[root][!value];
		}
		else {
			maxn=(maxn<<1);
			root=trie[root][value];
		}
	}
	return maxn;
}

哎,太菜了,所以写的啰里啰唆的QwQ,大佬请见谅

🍂全文完↩︎