cf1658D2

题目大意

给定两个数$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$的数量都相同。

所以我们不能再按照之前的思路。

答案一定存在于$l \oplus a_i (1 \le i \le n)$中，所以我们不妨试着验证$l \oplus a_i$是否为答案。

那么如何验证呢?

$x \oplus a_i$的结果，最大值就是$r$，最小值就是$l$

求一些数异或一个值的最大最小值为多少，这个问题可以用$trie$树解决。

代码

#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/cf1658D2/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！