2025.10.23 闲话-全局位运算 \(max\) 的解法
三部分将使用不同的策略求解。
Part.1 \(xor-max\)
这一类问题算是最简单的,每次插入一个数,在 \(Trie\) 树上跳,先查询这个数产生的最大值。
查询时如果当前位是 \(o\) 则优先向 \(!o\) 跳,再向 \(o\) 跳,容易证明一定是最优的(\(o\oplus(!o)=1\), \(o\oplus o=0\))。
查询完后直接插入 \(Trie\) 树即可。
复杂度 \(O(n\log V)\)。
Part.2 \(and-max\)
这类问题就比较困难了。
因为如果当前位是 1,那么可以大胆的跳 1,然后跳 0。
可是如果当前位是 0,就比较棘手了,因为可以跳 1,也可以跳 0,没有先后顺序,复杂度很容易变得很劣。
这时发现一件事,当前位是 0 时,如果 1 有两个或以上的点经过,那么这两个点一定会与出更优的答案,那么当前这个点就不用去遍历 1 的子树了!
那么只可能有一个点经过 1 时才搜,这时复杂度是 \(O(\log V)\) 的。
总复杂度就是 \(O(n\log^2 V)\),实测效率趋近较大常数 \(O(n\log V)\)。
另一种做法是暴力合并......这也是对的......(好像被创飞了😭😭😭😭😭😭😭😭😭😭😭😭😭😭)
又精心思考了一下,发现其实暴力合并和这个做法的本质是相同的。
Part.3 \(or-max\)
我不会,求教。