AcWing 143. 最大异或对( JavaScript )
原题链接
简单
作者:
gaobowen
,
2019-11-21 21:04:43
,
所有人可见
,
阅读 851
let idx = 0;//节点编号
//这里的 最坏的可能为310万。
let children = new Array(3100010);
// 数据量为10w时,这里初始化的时候会超时。
// for (let i = 0; i < children.length; i++) {
// children[i] = new Int32Array(2);//字符种类
// }
let inArr = [];
let max = 0;
// A1~AN 生成前缀树
let insert = x => {
let p = 0;//p当前节点编号,
for (let i = 30; i >= 0; i--) {
let u = x >> i & 1; // >>优先级高于&
if(children[p] === undefined) children[p] = [0,0];
// [p][u]表示获取当前节点的下一个节点的编号
if (!children[p][u]) children[p][u] = ++idx;
p = children[p][u];//获取下一个节点编号
}
}
let queryXOR = x => {
let p = 0;
let curr = 0;
for (let i = 30; i >= 0; i--) {
let u = x >> i & 1 ;
let w = u === 0 ? 1 : 0;
let k = 1 << i;
if(children[p][w]) {
curr += k;
p = children[p][w];
}
else if(max >= curr + k) return 0; //max的i位大于curr时,剪枝
else p = children[p][u];
}
return curr;
}
let buf = '';
process.stdin.on('readable', function () {
let chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
let getInputNums = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
process.stdin.on('end', function () {
let m = 0;
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx === 0) {
let a = getInputNums(line);
m = a[0];
} else if (lineIdx === 1) {
inArr = getInputNums(line);
inArr.forEach(x=>insert(x));
inArr.forEach(x=>{
max = Math.max(max, queryXOR(x));
})
console.log(max);
}
});
});