区块链系统app开发_八大员报名入口官网_seo工程师_山东自助seo建站

最大异或对

在给定的 N 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 N。

第二行输入 N 个整数 A1～AN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤$10^5$,
0≤Ai<$2^{31}$

输入样例：

3
1 2 3

输出样例：

3

【思路分析】

字典树（TrieTree），是一种树形结构，典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串,如01字典树）。主要思想是利用字符串的公共前缀来节约存储空间。很好地利用了串的公共前缀，节约了存储空间。字典树主要包含两种操作，插入和查找。

比如，我们要存储2(010)、4(100)、3(011)、6(110)、5(101)的二进制

这样我们要进行查找最大异或对时，无需进行二重循环，只需要枚举每个数，然后每个数按照从高位到低位找不同位的值，例如找与2(010)异或最大的值，从高位到低位

第一次寻找，2的最高位是0，寻找字典树中根节点的右孩子是否存在，存在则结果加上$2^2$

第二次寻找，2的次高位是1，寻找第一次寻找结点的左孩子是否存在，存在则结果加上$2^1$

第三次寻找，2的最低位是0，寻找第二次寻找到结点的右孩子是否存在，存在则结果加上$2^0$

最终异或后的结果是7(111)

而对于寻找，则需要知道每次结点的编号，因此在插入的时候，不妨记录每个结点的编号

import java.io.*;
import java.util.*;
public class Main {static final int N = 100010;static final int M = 3000010;//id是结点编号static int id = 0;static int[] arr = new int[N];static int[][] trie = new int[M][2];public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String row1 = br.readLine();int n = Integer.parseInt(row1);String row2 = br.readLine();String[] num = row2.split(" ");for(int i = 0; i < n; i++) {arr[i] = Integer.parseInt(num[i]);insert(arr[i]);}int res = 0;for(int i = 0; i < n; i++) {res  = Math.max(res, query(arr[i]));}System.out.println(res);br.close();}//构建字典树public static void insert(int x) {int k = 0;for(int i = 30; i >= 0; i--) {int bit = x >> i & 1;if(trie[k][bit] == 0) {trie[k][bit] = ++id;}k = trie[k][bit];}}public static int query(int x) {int k = 0, res = 0;for(int i = 30; i >= 0; i--) {int bit = x >> i & 1;//这一位能找到用来异或的数if(trie[k][bit ^ 1] != 0) {res += 1 << i;k = trie[k][bit ^ 1];} else{k = trie[k][bit];}}return res;}
}