CodeForces 1567B MEXor Mixup

题目链接:CodeForces 1567B MEXor Mixup

题目大意:
给定\(a\)、\(b\),求一个尽可能短的数组,使\(a\)是不属于该数组的最小非负整数,且该数组所有元素按位异或的结果为\(b\)。

题解:
易知\([0,a-1]\)均在该数组中,设\(x\)为\(0\bigoplus 1\bigoplus 2\bigoplus ...\bigoplus a-1\)的结果。

  1. 若\(b=x\),则数组为\(\{0,1,2,...,a-1\}\),数组长度为\(a\);
  2. 若\(b\bigoplus x \neq a\),则可以在数组中添加一个\(b\bigoplus x\),使\(x \bigoplus (b\bigoplus x)=b\),则数组为\(\{0,1,2,...,a-1,b\bigoplus x\}\),数组长度为\(a+1\);
  3. 若\(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;
}
上一篇:CF1557 C. Moamen and XOR


下一篇:C - Moamen and XOR