【Codeforces】1658D1 388535 (Easy Version) 题解

题目大意

给定两个数 $l, r$，将 $[l, l+1, \ldots, r-1, r]$ 的一个任意排列全部异或 $x$，得到一个新的数组 $a$。

给定 $l, r$ 和 $a$ 数组，求 $x$。

$$0 = l \le r \le 2^{17}$$

题目链接

思路

我们按位处理，计算异或前的数组每一位 $1$ 的个数，设为 $cntA$，计算异或后的数组每一位 $1$ 的个数，记为 $cntB$。

1. 那么一旦 $cntA_i \ne cntB_i$，$x$ 这一位一定为 $1$。
2. 如果 $cntA_i = cntB_i$，$x$ 这一位可以为 $1$，也可以为 $0$。

因为 $l = 0$，所以条件 2 总是成立：异或后的数组一定有一个 $x$，异或前有个 $0$，所以 $x$ 某一位为 $1$，那么异或后的数这一位 $1$ 的数量一定会变化。

而一旦 $l \ne 0$，那么就有可能 $1 \to 0$ 和 $0 \to 1$ 的数量相同而抵消，比如 $[1, 2] \oplus 2 = [0, 3]$，前后每一位 $1$ 的数量都相同（这是 hard version 需要处理的情况）。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int maxN = 1e5 + 7;

int T, l, r, cnt1[53], cnt2[53];

inline void calc(int *cnt, int x)
{
    int now = 0;
    while(x) {
        if(x & 1)
            cnt[now]++;
        now++; x >>= 1;
    }
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        memset(cnt1, 0, sizeof cnt1);
        memset(cnt2, 0, sizeof cnt2);
        scanf("%d%d", &l, &r);
        for(int i = l; i <= r; ++i) {
            calc(cnt1, i);
            int x; scanf("%d", &x);
            calc(cnt2, x);
        }
        int ans = 0;
        for(int i = 0; i < 31; ++i)
            if(cnt1[i] != cnt2[i])
                ans |= (1 << i);
        printf("%d\n", ans);
    }
    return 0;
}