题目链接 Problem - B - Codeforces

题意: 给出MEX 和 XOR(分别表示1. 本串数不存在的最小非负数  2. 本串数所有数异或后的结果)

求出这串数最少有几个数, 1 ≤ MEX ≤ 3⋅105; 0 ≤ XOR ≤ 3⋅105

解法: 首先MEX前面的数一定要有, 其次还需要几个数才能成功?

最简单的: 前面的数异或的结果(记为aa)=XOR, 输出结果就是前MEX个数(包含0)

其它一般情况来说, 此时只需要一个数就可以成功, 但是!!! MEX 是不能有的, 所以若aa^MEX == XOR就需要两个数异或得到MEX

总结: aa==XOR    结果: MEX

aa^MEX==XOR   结果: MEX+2

else               结果: MEX+1

附: 异或(^) 二进制表示数字相同为0, 不同为1

代码实现

#include
#include
#include
#include
#include
#include

int main()
{
for(int i = 1; i < 400000; i ++) a[i]= a[i-1]^i; int t; cin >> t;
while(t --)
{
cin >> b1>> b;
int res = a[b1-1];

     if(res == b)  
        cout << b1;  
     else if((res ^ b1) == b)  
        cout << b1+2;  
    else  
        cout << b1+1;  
    puts("");  
}

return 0;  

}

补充!!!

由于 MEX 的值为 a 那么说明 数组中存在 1 ~ a - 1 的这些元素 , 而通过计算 1 ^ 2 ^ 3 ^ 4…. ^ a - 1 我们会发现一个性质

int change(int n)
{
　　if(n == 1) return 0;
　　else if (n % 4 == 2) return 1;
　　else if(n % 4 ==3) return n;
　　else if(n % 4 == 1) return n - 1;
　　else if(n % 4 == 0) return 0;
}