AcWing 143. 最大异或对java
原题链接
简单
作者:
蜗牛爱吃草
,
2020-04-29 17:44:00
,
所有人可见
,
阅读 539
import java.io.*;
import java.util.StringTokenizer;
/**
* 求给定的一群数里的最大异或对
*/
public class Main {
static int M = 3000100;
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 u = x >> i & 1;
if (son[p][u] == 0){
son[p][u] = ++idx;
}
p = son[p][u];
}
}
public static int query(int x){
int p = 0;
int res = 0;
for (int i = 30; i >= 0; i--) {
int u = x >> i & 1;
if (son[p][1-u] != 0){
p = son[p][1-u];
res = res * 2 + 1-u;
}else{
p = son[p][u];
res = res * 2 + u;
}
}
return res ^ x;
}
private static class InputReader {
private static final int BUF_SZ = 65535;
private BufferedReader in;
private StringTokenizer st;
public InputReader(InputStream in) {
this.in = new BufferedReader(new InputStreamReader(System.in), BUF_SZ);
st = new StringTokenizer("");
}
public String next() throws IOException {
while(!st.hasMoreTokens()) {
try {
st = new StringTokenizer(in.readLine());
}catch (IOException e) {
throw new IOException(e);
}
}
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
private static InputReader in = new InputReader(System.in);
private static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
int n = in.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) {
int x = in.nextInt();
a[i] = x;
insert(x);
}
int max = 0;
for (int i = 0; i < n; i++) {
max = Math.max(max,query(a[i]));
}
System.out.println(max);
out.flush();
}
}
同学你为啥要自己重写输入函数?
是别人写的,貌似要快点。