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;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/86lu0v6k