本文共 1752 字，大约阅读时间需要 5 分钟。
知识点：Trie
在给定的N个整数A1，A2……ANA1，A2……AN中选出两个进行xor（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数N。
第二行输入N个整数A1A1～ANAN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤1051≤N≤105,
0≤Ai<2310≤Ai<231输入样例：
31 2 3
输出样例：
3
暴力写法超时
构建串树时间复杂度O(n)
数字的二进制，头部放在串树的头部，保证最大！
import java.io.*;import java.lang.Integer;class Main{ static int N = 3000010;//10^5 * 30位 static int[][] t = new int[N][2]; static int idx = 0; static void insert(int num){//构造串树 int p = 0; for(int x = 30; x >= 0; --x){ int c = num >> x & 1; if(t[p][c] == 0)t[p][c] = ++idx; p = t[p][c]; } } static int compare(int num){//比较当前数字的二进制数和串树，当前是0则找串树的1，否则找0，没有相反的情况那就找一样的 int p = 0; int max = 0; for(int x = 30; x >= 0; --x){ int c = num >> x & 1; if(t[p][c == 0 ? 1 : 0] == 0){ max = max << 1; p = t[p][c]; }else{ max = (max << 1) + 1; p = t[p][c == 0 ? 1 : 0]; } } return max; } public static void main(String[] args)throws Exception{ BufferedReader buf = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter buw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.valueOf(buf.readLine()); String[] params = buf.readLine().split(" "); for(int i = 0; i < n; ++i){ int num = Integer.valueOf(params[i]); insert(num); } int max = 0; for(int i = 0; i < n; ++i){ int num = Integer.valueOf(params[i]); int m = compare(num); max = Math.max(max, m); } buw.write(max + ""); buw.flush(); buf.close(); buw.close(); }}
转载地址：http://rkre.baihongyu.com/