【每日一题】补档 AGC015D A or...or B Problem | 构造

【每日一题】补档 AGC015D A or...or B Problem | 构造 | 困难

本文主要是介绍【每日一题】补档 AGC015D A or...or B Problem | 构造 | 困难，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目内容

原题链接

给定一个区间 $[A, B]$ ，从中选出两个数 $x$ 和 $y$ ， $x$ 可以等于 $y$ ，问 $x$ 或 $y$ 的结果可以得到多少个不同的数。

数据范围

$0\leq A\leq B<2^{60}$

题解

如果 $A = B$ ，那么答案就是 $1$ 。特判即可。

对于 $[A, B]$ 中的数， $A$ 和 $B$ 的二进制表示前缀中相同的部分或运算后的值必然是确定的，所以这部分可以不用考虑了。

举个例子： $A=13=1100_2,B=15=1111_2$ ，两者二进制都是以 $11$ 开头的，这部分就是确定的，故这部分可以不用考虑了。

可以将其重新设置为 $A=00_2,B=11_2$ 。

$B > A$ ，故两者从高位到低位的第一个不同的二进制数位 $k$ ， $k$ 必然是最高位。

那么我们可以把可选择的数 $x$ 和 $y$ 分为三部分，其中 $x\geq y$

选择 $x_k=0,y_k=0$ ，取值范围为： $A, 2^k-1]$
选择 $x_k=1,y_k=0$ ，取值范围为： $2^k+A, 2^{k+1}-1]$
选择 $x_k=1,y_k=1$ ，取值范围为： $2^k, 2^k+2^{s+1}-1]$ ，其中 $s$ 为从高位到低位第二个为 $1$ 的二进制位，当不存在时， $s = - 1$ 。

对于 $x_k=0,y_k=0$ ，由于取值最小值为 $A$ ，取值最大值为 $2^k-1$ ，故或运算的值必然在这个范围内。
具体构造出值 $v\in[A, 2^k-1]$ ，令 $x = y = v$ 即可。

对于 $x_k=1,y_k=0$ ，第 $k$ 位或运算结果为 $1$ ，那么只需要考虑低 $k - 1$ 位。因为 $y\geq A$ ，所以或运算的结果必然 $\geq A$ ，但是低 $k - 1$ 位至多是全部为 $1$ ，即 $2^k-1$ 。
具体构造出值 $v\in[2^k+A, 2^{k+1}-1]$ ，令 $x=2^k,y=v-2^k$ 即可。

对于 $x_k=1,y_k=1$ ，如果 $B=2^k$ ，那么只能选择一个数。
否则 $B>2^k$ ， $s$ 为从高位到低位第二个为 $1$ 的二进制位。

对于 $bit\in(s,k)$ 的二进制位 $bi t$ ，这些必然不可能为 $1$ 。
那么 $v_k,v_{k-1},\cdots,v_{s+1}$ 这些二进制位都已确定。那么可以构造出 $2^k, 2^k+2^{s+1}-1]$ 。
具体构造出值 $v\in[2^k, 2^{k}+2^{s+1}-1]$

当 $v<2^{k}+2^{s+1}-1$ ， $x=v,y=2^k$
当 $v=2^{k}+2^{s+1}-1$ ， $x=2^k+2^{s},y=2^k+2^{s}-1$

当然，这里的 $x_k=1,y_k=0$ 和 $x_k=1,y_k=1$ 的取值区间可能会有交集。

因为 $2^k<2^k+A$ ，所以必然是 $2^{k}+2^{s+1}-1\geq 2^k+A$ ，即 $2^{s+1}-1\geq A$ ，即 $2^{s+1}>A$ ，此时 $A$ 的二进制为 $1$ 的最高位小于等于 $B$ 的二进制为 $1$ 的次高位。

时间复杂度： $O(\log \max(A,B))$ ，至多 $60$

代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);ll A, B;cin >> A >> B;if (A == B) {cout << "1\n";return 0;}vector<int> vecA(60), vecB(60);for (int i = 0; i < 60; ++i) {vecA[i] = A % 2;vecB[i] = B % 2;A /= 2;B /= 2;}while (!vecA.empty() && vecA.back() == vecB.back()) {vecA.pop_back();vecB.pop_back();}int n = int(vecA.size());reverse(vecA.begin(), vecA.end());reverse(vecB.begin(), vecB.end());int s = -1;for (int i = 1; i < vecB.size(); ++i) {if (vecB[i] == 1) {s = n - 1 - i;break;}}ll ans = 0;A = 0;for (int i = 0; i < vecA.size(); ++i) A = A * 2 + vecA[i];ll R = (1ll << (n - 1)) + (1ll << (s + 1)) - 1;ll L = A;if (R >= (1ll << (n - 1)) + A) {R = (1ll << n) - 1;ans = R - L + 1;} else {ans = R - L + 1;ans += (1ll << (n - 1)) - 1 - A + 1;}cout << ans << "\n";return 0;
}