题目描述
在给定的N个整数A1,A2……AN中选出两个进行xor(异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数N。
第二行输入N个整数A1~AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤105,
0≤Ai<231
输入样例:
3
1 2 3
输出样例:
3
思路
1.暴力求解
int res = 0;
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
res = max(res, a[i] ^ a[j])
}
}
显然暴力求解在数的范围特别大的时候,O(n^2)很容易超时
2.trie树构建
任何一个数字,范围在2的31次方上。所以我们通过构造trie树进行优化,将n优化成logn,
将所有的数字按照从高位到低位以二进制字符串的方式,将其用tire构造出来
其中从高到低构建trie树原因是本题要求最大异惑值,所以从高位点找异或值能够保证整体res的结果最大
构造方法见 https://www.acwing.com/solution/content/33114/
异或^的特点 相同为0, 不同为1
所以对于每一个元素a[i],从trie树中找最大的异或值,需要a[i]从高到低找其位置相异的位
比如 1 2 3
1 : 01
2 : 10
3 : 11
trie树
idx 0 1
0 0(idx=1) 1(idx=3)
| |
|___________|
| |
| V
1 | 1(idx=2)
| 01结束
|
|
2 |
|
|
3 0(idx=4)<————————>1(idx=5)
10结束 11结束
01 : p = 0
0 -> 1 son[0][1]存在 p转到节点3
1 -> 0 son[3][0]存在
01 ^ 10 = 11 = 3
10 : p = 0
1 -> 0 son[0][0]存在 p转到节点1
0 -> 1 son[1][1]存在
10 ^ 01 = 11 = 3
11 : p = 0
1 -> 0 son[0][0]存在 p转到节点1
1 -> 0 son[1][0]不存在 1 -> 1 son[1][1]存在
11 ^ 01 = 10 = 2 末尾都为1,异或值为0,这也说明了代码中为什么在找到相同位,不参与res运算
结束
java
import java.io.*;
public class Main{
static int n;
static int N = 100010; // 一个数字可能存在的最大缩影idx
static int M = 31 * N; //31位 * 数字个数
static int[][] son = new int[M][2];
static int idx = 0;
public static void insert(int x){
int p = 0;
for(int i = 30; i >= 0; i --){
int s = x >> i & 1;
if(son[p][s] == 0) son[p][s] = ++ idx;
p = son[p][s];
}
}
public static int query(int x){
int p = 0;
int res = 0;
for(int i = 30; i >= 0; i --){
int s = (x >> i & 1) == 1 ? 0 : 1; // 对立的
if(son[p][s] != 0){
res += 1 << i;
p = son[p][s];
}else{
s = (s == 1 ? 0 : 1;) //返回到正常的
p = son[p][s];
}
}
return res;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
String[] str = br.readLine().split(" ");
for(int i = 0; i < n; i ++){
insert(Integer.parseInt(str[i]));
}
int res = 0;
for(int i = 0; i < n; i ++){
res = Math.max(res, query(Integer.parseInt(str[i])));
}
bw.write(res + " ");
bw.flush();
bw.close();
br.close();
}
}
python3
N = 100010
M = 31 * N
n = 0
son = [[0] * 2 for i in range(M)]
idx = 0
def insert(x):
global son, idx
p = 0
for i in range(30, -1, -1):
s = x >> i & 1
if(son[p][s] == 0):
idx += 1
son[p][s] = idx
p = son[p][s]
def query(x):
global son
p = 0
res = 0
for i in range(30, -1, -1):
s = x >> i & 1
if(s == 0): s = 1
else: s = 0
if(son[p][s] != 0): #如果对立的边存在
res += 1 << i
p = son[p][s]
else:
if(s == 0): s = 1
else: s = 0
p = son[p][s]
return res
def main():
n = int(input())
s = list(map(int, input().rstrip().split(" ")))
for i in range(n):
insert(s[i])
res = 0
for i in range(n):
res = max(res, query(s[i]))
print(res)
main()
c++
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 31 * N; //int
int n;
int son[M][2], idx;
int a[N];
void insert(int x){
int p = 0;
//技巧,i = -1 机器码为11 ~i 00 表示 i == 0
for(int i = 30; i >= 0; i--){
int s = x >> i & 1; //0 or 1
if(!son[p][s]) son[p][s] = ++ idx;
p = son[p][s];
}
}
int query(int x){
int res = 0, p = 0;
for(int i = 30; ~i; i --){
int s = x >> i & 1;
if(son[p][!s]){ //如果1, 0对立的0,或者1存在,就可以实现最大化
res += 1 << i;
p = son[p][!s];
}
else p = son[p][s]; //没有,就是0^0 = 0, 1^1 = 0, 最终res += 0
}
return res;
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++){
cin >> a[i];
insert(a[i]);
}
int res = 0;
for(int i = 0; i < n; i ++) res = max(res, query(a[i]));
cout << res << endl;
return 0;
}
语法笔记: 查询(遍历)Trie用的query函数中:
[!s]
即[s] != 0
,然后一直都是把 blah[blah][s]设为1,所以对应的就都是判断0. (来满足异或成1, 注:2进制中,一比零大(好像无论啥进制都是如此))trie树的查询判定条件依赖列的数值,每次x的二进制数为1,则找列为0即可,同理,为0,找1