CF2077B Finding OR Sum 题解

Sol $1$. 用 $O(\log n)$ 次询问计算答案。

首先肯定要询问一下 $0$，此时可以求得 $x+y$ 的值。然后对于每一个二进制位 $i$ 询问 $2^i$ 的值。此时设回答的值为 $o$，则：

• 若 $x+y=o$，则此时 $x,y$ 二进制第 $i$ 位都没有改变，那么 $x,y$ 二进制下第 $i$ 位的值都为 $1$。
• 若 $o-x-y=2\times 2^i$，则此时 $x,y$ 二进制下的第 $i$ 位的值都必须改变，那么 $x,y$ 二进制下第 $i$ 位的值都为 $0$。
• 否则必有 $o-x-y=2^i$，则此时 $x,y$ 二进制下的第 $i$ 位的值恰有一个是 $1$。因为 $x,y$ 每一位的值互相独立且其实并不需要知道其值具体是多少，因此钦定此时 $x$ 第 $i$ 位为 $1$，$y$ 第 $i$ 位为 $0$。

然后直接把 $x,y$ 和答案计算起来即可，询问此时为 $31$ 即 $O(\log n)$。

Sol $2$. 用 $3$ 次询问计算答案。

询问 $0$ 的步骤看上去不太能省，因此考虑优化对每一个二进制位的询问。考虑为什么不能把所有二进制位一起询问即询问 $2^{30}-1$。很显然这样的话 $o-x-y=2\times 2^i$ 的情况是困难区分的，可能会和其上一位恰有一个 $1$ 的情况混淆。因此考虑隔一个位询问一个 $1$，这样每一次拿出二进制中相邻两个位的值讨论，这个值必然是 $0,1,2$ 中的一个。因此只需要再询问两次，分别为 $(010101\ldots0101)_2$ 和 $(101010\ldots1010)_2$。

Sol $3$. 用 $2$ 次询问计算答案。

看上去 Sol $2$ 已经很优秀了，考虑还有哪里可以优化。发现若询问 $(111\ldots111)_2$ 的值，那么不论 $x,y$ 的值如何取，答案是可以直接计算出的，就是 $2\times(2^{30}-1)$。然后又可以发现 Sol $2$ 中两次非 $0$ 询问的每一个位都不同，因此我们设第一次非 $0$ 询问的值为 $a$，第二次非 $0$ 询问的值为 $b$，$0$ 询问的值为 $x$，$t=2\times(2^{30}-1)$。则此时根据容斥原理必有 $a+b-x=t$。询问 $a,x$ 的值，而 $t$ 的值为定值，可以直接解得 $b$ 的值。因此此时只需要询问 $2$ 次，可以通过问题。

讲的可能很混乱，建议结合 代码 理解。顺便提醒一下，注意一下位运算的时候的细节，不要因为少加一个 $1$ 调试 1h（