很菜，div4打三百多名，不过排名跟第一场div4没什么变化hhh，不过打着打着，是真菜。
G. Even-Odd XOR
题意：给你$n$，你需要构造$n$个不同数字的序列，要求满足奇数项的异或和和偶数项的异或和相等。
思路：
假如七个数a,b,c,d,e,f,g需要满足
$$
a\oplus c\oplus e\oplus g=b\oplus d\oplus f
$$
因为异或有公式a^a=0所以可以“移项”变成：
$$
a\oplus b\oplus c\oplus d\oplus e\oplus f\oplus g=0
$$
也就是题目要求给你$n$，需要你构造$n$个不同的数字异或和为0。
问题主要是在这个"不同"上面。
我可以直接构造$n-3$个$1...n-3$，还有三位数分别是$2^{30}$,$2^{29}$,以及$x$。
$x$为前面$n-1$个数字的异或和。$x=1\oplus 2\oplus 3\oplus ...\oplus 2^{30}\oplus 2^{29}$。这经过这个$x$之后，所有的$n$个数字都能异或为$0$。
这样不同吗？一定不同，因为的$x$至少得有$2^{30}\oplus 2^{29}$，这还得跟前面$n-3$个数字异或，这样肯定不是与$n-3$会装，也不会和后面两个撞。
那么我可以用一个数字嘛？比如让前面$n-2$放，最后两个来操作，答案是不可以的，这样可能导致这两个数字相等（只要前面$n-2$个数字异或和为$0$就会这样）。
代码：
inline void Case_Test()
{
cin>>n;
a[n] = 0;
int &x = a[n];
for (int i=1;i<=n-3;i++) a[i] = i, x^=i;
a[n-2] = 1<<30;
a[n-1] = 1<<29;
x^=a[n-2]^a[n-1];
for (int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
其他总结
全局变量需要进行下一次数据的时候记得clear，记得初始化
文章评论