Codeforces Round #742 (Div. 2) B. MEXor Mixup

Codeforces Round #742 (Div. 2)的其他题解点这

B. MEXor Mixup

原题链接

题目大意：

让你构造一个 mex 为a，xor和为b的序列

问最小的序列长度

思路：

首先因为mex为a，所以[0,a-1]都是必须选的

我们可以预处理出他的异或和sum

如果sum[ a - 1 ] = b 那么答案是 a

对于不等于的，我们都能找到一个数与其异或得到b

但是还需要考虑其mex是否不为a，也就是 b ^ sum[ a - 1 ]恰好就是 a

这时候我们就必须两个数了

如果( sum[ a - 1 ] ^ b ) = a 那么答案就是a + 2

如果不等于则是 a + 1

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#define ll long long 
using namespace std;
const int maxn = 1e7 + 3;
int sum[maxn];
int main() {
	int T;
	scanf("%d", &T);
	for (int i = 1; i <= 3e5; ++i) {
		sum[i] = sum[i - 1] ^ i;
	}
	while (T--) {
		int a, b;
		scanf("%d %d", &a, &b);
		if (sum[a - 1] == b)printf("%d\n", a);
		else if ((sum[a - 1] ^ b) == a)printf("%d\n", a + 2);
		else printf("%d\n", a + 1);
	}
}