【题解】CF2077B Finding OR Sum
本文发布于博客园和洛谷，若您在其他平台阅读到此文，请前往博客园获得更好的阅读体验。跳转链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18771334。
思路
关于此题，我们首先对 \(n | x\) 变一下形，\(n | x = n + (x \& \sim n)\)，也就是把 \(n\) 和 \(x\) 同时为 \(1\) 的位在 \(x\) 中删掉，这样的话，为 \(1\) 的位要么在 \(n\)，要么在 \(x\)，因此我们可以得出 \((x \& \sim n) + (y \& \sim n) = (n | x) + (n | y) - 2 \times n\)。
我们要得到 \((m | x) + (m | y)\) 的值，只需要把每一位上 \(x\) 和 \(y\) 的 \(1\) 的出现数量情况找出来，再根据 \(m\) 的每一位是 \(1\) 还是 \(0\) 来模拟或运算以及位运算即可。
那么我们如何在两次询问的情况下，把每一位的 \(1\) 的出现数量找出来呢？
我们注意到，在二进制位的情况下相加，当前位为第 \(i\) 位，如果第 \(i + 1\) 位和 \(i - 1\) 位都是 \(0\)，则两个数的第 \(i\) 位相加只会有这两种情况：
[*]两个 \(1\)：第 \(i + 1\) 位为 \(1\)，第 \(i\) 位为 \(0\)。
[*]两个 \(0\)：第 \(i + 1\) 位和 第 \(i\) 位均为 \(0\)。
[*]一个 \(1\) 一个 \(0\)：第 \(i\) 位为 \(1\)，第 \(i + 1\) 位为 \(0\)。
那么，我们就可以根据上面那个式子，求一次奇数位全部变成 \(0\) 的两个数的和，把偶数位的 \(1\) 的出现次数情况求出来，求一次偶数位全部变成 \(0\) 的两个数的和，把奇数位的 \(1\) 的出现次数情况求出来。
然后，根据下面的规则逐位求解：
[*]如果 \(m\) 第 \(i\) 位为 \(1\)，那么这一位对答案的贡献就是 \(1 \ll (i + 1)\)。
[*]如果 \(m\) 第 \(i\) 位为 \(0\)，那么这一位对答案的贡献就看 \(1\) 的出现次数，如果出现次数为 \(2\)，那就是 \(1 \ll (i + 1)\)，如果出现次数为 \(1\)，那就是 \(1 \ll i\)。
AC CODE
#include #define inf 2e18#define int long longconst int N = 2e5 + 9;int ask(int x) { std::coutop; return op;}void solve(){ std::vector a(30); int tmp = 0; for(int i = 0;i < 30;i += 2) { tmp |= (1ll
页:
[1]