题目链接:CodeForces 1567B MEXor Mixup
题目大意:
给定\(a\)、\(b\),求一个尽可能短的数组,使\(a\)是不属于该数组的最小非负整数,且该数组所有元素按位异或的结果为\(b\)。
题解:
易知\([0,a-1]\)均在该数组中,设\(x\)为\(0\bigoplus 1\bigoplus 2\bigoplus ...\bigoplus a-1\)的结果。
- 若\(b=x\),则数组为\(\{0,1,2,...,a-1\}\),数组长度为\(a\);
- 若\(b\bigoplus x \neq a\),则可以在数组中添加一个\(b\bigoplus x\),使\(x \bigoplus (b\bigoplus x)=b\),则数组为\(\{0,1,2,...,a-1,b\bigoplus x\}\),数组长度为\(a+1\);
- 若\(b\bigoplus x = a\),则不能直接在数组中添加\(b\bigoplus x\),需要改成\(b\bigoplus x\bigoplus 1\)和\(1\),使\(x \bigoplus (b\bigoplus x\bigoplus 1)\bigoplus 1=b\),则数组为\(\{0,1,2,...,a-1,b\bigoplus x\bigoplus 1,1\}\),数组长度为\(a+2\)。
#include <iostream>
using namespace std;
int t, a, b, Xor;
int main() {
cin >> t;
while (t--) {
cin >> a >> b;
if (a % 4 == 1) Xor = a - 1;
else if (a % 4 == 2) Xor = 1;
else if (a % 4 == 3) Xor = a;
else Xor = 0;
if (b == Xor) cout << a << endl;
else if ((b ^ Xor) != a) cout << a + 1 << endl;
else cout << a + 2 << endl;
}
return 0;
}