MEXor Mixup（源地址自?CF742B）
Problem
Alice gave Bob two integers \(a\) and \(b\) ( \(a>0\) and \(b≥0\) ). Being a curious boy, Bob wrote down an array of non-negative integers with \(MEX\) value of all elements equal to \(a\) and \(XOR\) value of all elements equal to \(b\) .
What is the shortest possible length of the array Bob wrote?
Recall that the \(MEX\) (Minimum EXcluded) of an array is the minimum non-negative integer that does not belong to the array and the \(XOR\) of an array is the bitwise \(XOR\) of all the elements of the array.
Input
The input consists of multiple test cases. The first line contains an integer \(t\) ( \(1≤t≤5*10^4\) ) — the number of test cases. The description of the test cases follows.
The only line of each test case contains two integers \(a\) and \(b\) (\(1≤a≤3*10^5\) ; \(0≤b≤3*10^5\) ) — the \(MEX\) and \(XOR\) of the array, respectively.
Output
For each test case, output one (positive) integer — the length of the shortest array with \(MEX\) \(a\) and \(XOR\) \(b\) . We can show that such an array always exists.
Example
5
1 1
2 1
2 0
1 10000
2 10000
3
2
3
2
3
Note
In the first test case, one of the shortest arrays with \(MEX\) \(1\) and \(XOR\) \(1\) is
[0,2020,2021].
In the second test case, one of the shortest arrays with \(MEX\ 2\) and \(XOR\ 1\) is[0,1].
It can be shown that these arrays are the shortest arrays possible.
题意
现在有 \(a\) 、 \(b\) 两个限定条件，求解出最短的数组，满足：
1 . 数组内元素必须是 \(>0\) 的。
2 . \(a\) 是数组中没有出现过的最小正整数
3 . 数组中所有元素的按位异或和恰好等于 \(b\) 。
输出数组的最短长度。
思路：
由条件1和2可知：数组内必定包含 \(a\) 个数，且为
[0,1,2,……,a-1]。
由所有元素的按位异或和可知：在没有限制的条件下，对于已有的数据 \(b1\) ，要得到指定的数据 \(b2\) ，仅有两种情况可以讨论：
1 . \(b1==b2\) ，此时，直接输出即可。
2 . \(b1!=b2\) ，此时，容易证明，一定能找到一个数字 \(k\) ，使得 \(k\) 异或 \(b1\) 答案为 \(b2\) 。
由条件3可知：限制条件在于 \(k\) 不能等于 \(a\) ，若等于，则需要另外寻找两个数字再来异或和（例如样例数据1）。
所以综上可知，需要先计算出 \(0\) 至 \(a\) \((a=(0,1,2,…,3*10^5))\) 所有数字的异或和。此后，对于每一组读入的 \(a\ b\) ，
AC代码：
//A WIDA Project
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct fx{
ll x,y,w;
}a[1000005];
ll n,ans;
bool cmp(fx x,fx y) return x.w>y.w;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&a[i].x,&a[i].y);
a[i].w=a[i].x-a[i].y;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++) ans+=a[i].w*i-a[i].x+n*a[i].y;
printf("%d\n",ans);
return 0;
}
错误次数：1次
原因：未开long long