cf1658D1 388535 (Easy Version) 题解

题目大意

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

给定\(l, r\)和\(a\)数组，求\(x\)。

其中\(0 = l \le r \le 2^{17}\) 题目链接 ## 思路

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

1. 那么一旦\(cntA_i != cntB_i\),那么就说明\(x\)这一位一定为\(1\)

2. 对于\(cntA_i == cntB_i\)一样的位数，说明这一位可以为\(1\),也可以为\(0\)。

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

而一旦\(l \not = 0\),那么就有可能\(1\)变为\(0\),\(0\)变为\(1\)的数量相同，抵消掉了，比如\([1,2] \oplus 2 = [0,3]\),前后每一位\(1\)的数量都相同。

代码

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

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/03/31/cf1658D1/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！