MEXor Mixup（思维题）

题目

MEXor Mixup

问题描述

给定两个值$a$跟$b$，满足$a>0$,$b\ge 0$
若有一个非负整数数组，使得其中所有元素经过Mex运算的结果为$a$，其中所有元素经过XOR操作的结果为$b$
问满足这些条件的数组的最小长度为多少。

分析

关于$Mex$运算的内容可以见于我之前的博客——SG函数介绍

mex（S）表示不属于集合S的最小非负整数。

也就是在非负整数中，先除去S，然后在剩余的非负整数中取最小值。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

若mex{S}为$a$，就说明小于$a$的非负整数已经包含在数组当中了,也就是说，这个数组至少包含了小于$a$的$a$个非负整数且不包含元素$a$，至于大于$a$的元素，还不清楚。

接下来就是对条件二的讨论:所有元素经过XOR操作的结果为$b$。
设数组C用来储存前缀异或和，那么就可以分出三种情况，
情况一：C[a-1]==b,意味着无需额外的元素就满足了条件二，输出a即可；

情况二：C[a-1]==a,意味着所需要的那个元素恰好为不可取的a，那么就需要用另外两个元素异或的结果来替代这个元素，输出a+2;

情况三；C[a-1]!=a,意味着所需要的那个元素可以直接加入数组，所以输出a+1即可。

代码

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
int t;
int a,b;
int c[300006];
int main(){
    for(int i=1;i<300006;i++){
    c[i]=c[i-1]^i; }while(cin>>t){
    while(t--){
    cin>>a>>b;if(c[a-1]==b)cout<<a;else if((c[a-1]^b)==a)cout<<a+2;else cout<<a+1;cout<<endl;}}return 0;
}