写完ac后试了下最高赞的java题解的代码
发现我这个比他速度要快一倍多
思路:
用一个这样的东西来存数
class Tree {
Tree[] kid = new Tree[2];
public void add(int val) {
Tree o = this;
for (int i = 30; i >= 0; i--) {
int x = (1 << i & val) == 0 ? 0 : 1;
if (o.kid[x] == null) o.kid[x] = new Tree();
o = o.kid[x];
}
}
}
然后 找出最大的2的幂 k 并且这个k要比最大的数要小于等于
比如 给出的数中最大值是80 那么k就是64
如果是150 那么k就是128
然后dfs找出所有大于等于k的数
然后对于每一个dfs出来的数
在存起来的数中再找到二进制从左往右对应的位置尽可能不同的那个数
比如 有一个数是123
二进制形式是:
1111011 最理想的情况是能找出二进制形式为:
0000100 的数 即4
这时结果 123^4 就是最大的127
然后遍历即可
import java.io.*;
class Main {
static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int res = 0;
static Tree tree = new Tree();
public static void main(String[] args) throws IOException {
int n = in();
while (n-- > 0) tree.add(in());
Tree o = tree;
int idx = 30;
while (o.kid[1] == null) {
o = o.kid[0];
--idx;
}
dfs(o.kid[1], idx - 1, 1 << idx);
System.out.println(res);
}
public static void dfs(Tree o, int idx, int val) {
if (idx == 0) {
if (o.kid[1] != null) val |= 1;
o = tree;
int another = 0;
for (int i = 30; i >= 0; --i) {
int x;
if (o.kid[1] == null) x = 0;
else if (o.kid[0] == null) x = 1;
else x = (1 << i & val) == 0 ? 1 : 0;
if (x == 1) another |= 1 << i;
o = o.kid[x];
}
res = Math.max(res, val ^ another);
return;
}
if (o.kid[1] != null) dfs(o.kid[1], idx - 1, val | (1 << idx));
if (o.kid[0] != null) dfs(o.kid[0], idx - 1, val);
}
public static int in() throws IOException {
sc.nextToken();
return (int) sc.nval;
}
}
class Tree {
Tree[] kid = new Tree[2];
public void add(int val) {
Tree o = this;
for (int i = 30; i >= 0; i--) {
int x = (1 << i & val) == 0 ? 0 : 1;
if (o.kid[x] == null) o.kid[x] = new Tree();
o = o.kid[x];
}
}
}