异或最大值
time limit per test 2 second memory limit per test 256 megabytes
给定一些数,求这些数中两个数的异或值最大的那个值

传送门:CSUOJ1216

Input

多组数据。第一行为数字个数n,1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。

Output

任意两数最大异或值

Sample Input

1
2
3
4
3
3
7
9

Sample Output

1
14

题解

trie树上的贪心,从高位到低位建好树后优先贪心每位能异或出1的
## AC code:(不包含输入类)
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import java.io.*;  
import java.util.*;
public class Main {

public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
PrintWriter pw=new PrintWriter (System.out);
while(sc.hasNext()){
int n=sc.nextInt();
int[]shu=new int[n];
for(int i=0;i<n;i++){
shu[i]=sc.nextInt();
}
Trie trie=new Trie();
for(int i=0;i<n;i++){
String s=makeString(shu[i]);
//pw.println(s);
Trie temp=trie;
for(int j=0;j<s.length();j++){
int k=s.charAt(j)-'0';
if(temp.trie[k]==null){
temp.trie[k]=new Trie();
temp=temp.trie[k];
}else{
temp.trie[k].count++;
temp=temp.trie[k];
}
}
}
//pw.println(trie.trie[1]);
int max=-1;
for(int i=0;i<n;i++){
String s=makeString(shu[i]);
//pw.println(s);
Trie temp=trie;
StringBuilder t=new StringBuilder();
for(int j=0;j<s.length();j++){
int k=s.charAt(j)-'0';
//pw.print(k);
if(temp.trie[k^1]!=null){
temp=temp.trie[k^1];
t.append(1);
}else{
temp=temp.trie[k];
t.append(0);
}
}
//pw.println(t.toString());
max=Math.max(max, js(t.toString()));
}
pw.println(max);
pw.flush();
}

}
static int js(String s){
int k=0;
for(int i=s.length()-1;i>=0;i--){
if(s.charAt(i)=='1')
k=k+(int)Math.pow(2,31-i);
}
return k;
}
static String makeString(int temp){
StringBuilder sb=new StringBuilder();
while(temp>0){
if(temp%2==1){
sb.append(1);
}else{
sb.append(0);
}
temp=temp/2;
}
sb.reverse();
while(sb.length()<32){
sb.insert(0, '0');
}
return sb.toString();
}
}
class Trie{
int count;
Trie[] trie;
Trie(){
this.count=1;
trie=new Trie[2];
}
}