【题解】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 <bits/stdc++.h> #define inf 2e18 #define int long long  const int N = 2e5 + 9;  int ask(int x) {     std::cout << x << std::endl;     int op;std::cin >> op;     return op; }  void solve() {     std::vector<int> a(30);      int tmp = 0;     for(int i = 0;i < 30;i += 2) {         tmp |= (1ll << i);     }          int res1 = ask(tmp) - tmp * 2;     for(int i = 1;i < 30;i += 2) {         if(res1 & (1ll << (i + 1))) {             a[i] = 2;         } else if(res1 & (1ll << i)) {             a[i] = 1;         } else {             a[i] = 0;         }     }      tmp = 0;     for(int i = 1;i < 30;i += 2) {         tmp |= (1ll << i);     }      int res2 = ask(tmp) - tmp * 2;     for(int i = 0;i < 30;i += 2) {         if(res2 & (1ll << (i + 1))) {             a[i] = 2;         } else if(res2 & (1ll << i)) {             a[i] = 1;         } else {             a[i] = 0;         }     }      std::cout << '!' << std::endl;      int ck;std::cin >> ck;      int ans = 0;     for(int i = 0;i < 30;i ++) {         if(ck & (1 << i)) {             ans += (1ll << (i + 1));         } else if(a[i] == 2) {             ans += (1ll << (i + 1));         } else if(a[i] == 1) {             ans += (1ll << i);         }     }      std::cout << ans << std::endl; }