CF1493E Enormous XOR 题解
题目链接:Enormous XOR
题意:
定义 \(g(x,y) = x \oplus (x+1) \oplus \dots \oplus (y-1) \oplus y\) 。
设 \(f(l,r)\) 为所有满足 \(l\leq x\leq y\leq r\) 的 \(g(x,y)\) 的最大值。
先给出 \(l,r\) 的二进制形式,求 \(f(l,r)\) 。
数据范围:
\(1 \le n \le 10^6\) 。其中 \(n\) 是 \(l,r\) 二进制下的位数。
找规律猜结论题。
注意到如果 \(l,r\) 的位数不同,答案必定为 \(2^n-1\) ,令 \(x=2^{n-1}-1,\,y=2^{n-1}\) 即可
接下来考虑 \(l,r\) 位数相同的情况。这里有一个结论,当 \(x\) 是偶数时,\(x \oplus (x + 1)=1\) 。
于是 \(\bigoplus_{i=0}^{2k+1}(x + i)\) 的值为 \(0\) ,因为两两相互抵消了。考虑利用这个性质。
可以证明,原题的答案的取值只可能是 \(x,\,x - 1,\,y,\,y + 1\) (这里的 \(x,y\) 是题目里的)。
- 当 \(x\) 为奇数且 \(y-x \equiv 0 \pmod{4}\) 时,答案为 \(x\) 。
- 当 \(x\) 为奇数且 \(y-x \equiv 2 \pmod{4}\) 时,答案为 \(x \oplus 1\) 。也就是 \(x-1\) 。
- 当 \(x\) 为偶数且 \(y-x \equiv 0 \pmod{4}\) 时,答案为 \(y\) 。
- 当 \(x\) 为偶数且 \(y-x \equiv 2 \pmod{4}\) 时,答案为 \(y \oplus 1\) 。也就是 \(y + 1\) 。
显然当 \(y=r\) 时答案最大,并且我们希望取到 \(y+1\) 。
- 当 \(r\) 是奇数时,无法得到更好的答案,因此取 \(x=y=r\) 。
- 当 \(r\) 是偶数时,只需要 \(l+2 \le r\) 即可令 \(x=l+2,\,y=r\) 。
时间复杂度 \(\mathcal{O}(n)\)
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e6 + 15))
char l[N], r[N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n; cin >> n >> (l + 1) >> (r + 1);
if(l[1] != r[1]) { rep(i, 1, n) { cout << '1'; } return 0; }
if(r[n] & 1) return cout << (r + 1) << '\n', 0;
++l[n - 1];
Rep(i, n - 1, 0) if(l[i] > '1') l[i] -= 2, ++l[i - 1];
bool ok = false;
rep(i, 0, n) if(l[i] != r[i]) { ok = l[i] < r[i]; break; }
r[n] += ok; cout << (r + 1) << '\n';
return 0;
}
参考文献: