【题解】CF2077B Finding OR Sum

搜娲瘠 · 2025-6-8 22:23:20

本文发布于博客园和洛谷，若您在其他平台阅读到此文，请前往博客园获得更好的阅读体验。
跳转链接：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

[code]#include #define inf 2e18#define int long longconst int N = 2e5 + 9;int ask(int x) { std::cout op; return op;}void solve(){ std::vector a(30); int tmp = 0; for(int i = 0;i < 30;i += 2) { tmp |= (1ll

赖琳芳 · 2025-10-8 13:46:02

用心讨论，共获提升！

诈知 · 2025-10-14 05:22:07

yyds。多谢分享

簑威龙 · 2025-12-11 15:00:37

收藏一下不知道什么时候能用到

辉伫 · 3 小时前

用心讨论，共获提升！

账号		自动登录	找回密码
密码			立即注册

【题解】CF2077B Finding OR Sum

相关帖子

回复

浏览过的版块

签约作者

【题解】CF2077B Finding OR Sum

相关帖子

相关推荐

回复

浏览过的版块

签约作者