「yyOI R1」youyou 的异或 题解
youyou2007
·
·
题解
这里是出题人题解。
Solution
5pts
随便手模两下即可算出 n \le 5 的情况，注意 n=3 无解即可得分。
15pts
可以通过各种奇奇怪怪的爆搜来通过 n \le 10 的数据。
40pts
给一些 O(n^2) 的算法通过的数据，但我没有想出来怎么用这个复杂度构造。
100pts
异或均用 \oplus 代替。
做本题前需要先明确几个比较简单的性质：（a 是正整数）
- 性质 1：如果 a 为偶数，那么 a \oplus (a+1)=1。
这个性质很好理解：a 与 a+1 只有最低位是不同的，所以异或以后为 1。
明确了上述性质，我们很快会有一个想法：可以考虑将一个偶数与比该偶数多 1 的奇数视为一组，这样每一组的异或和为 1。而每两组的异或和为 0。
即，当 a 是偶数时，a \oplus (a+1)=1，a \oplus (a+1) \oplus (a+2)\oplus (a+3)=0。
发现两组是 4 个数，根据 n \% 4 的余数进行分类讨论构造：
考虑构造序列 \{1,2,3,4,...,n\}。因为除 1 与 n 以外，剩下的数为 4k + 2 个，为 2k+1 组，所以除 1 与 n 以外的其他数异或和为 1 ，再有 1 \oplus 1\oplus n = n，所以构造成立。
例如 n = 8 时可以构造序列为 \{a\} = \{1,2,3,4,5,6,7,8\}。
考虑构造序列 \{2,3...,n-2,n,n+1,n+2\}，因为除 n 以外，剩下的数为 4k 个，可以分成 2k 组，所以异或和为 0，再有 0 \oplus n = n，所以构造成立。
例如 n = 9 时可以构造序列为 \{a\} = \{2,3,4,5,6,7,9,10,11\}。
考虑构造序列 \{1,2,3,...,n-1,n+1\}，因为除 1 与 n + 1 以外，剩下的数为 4k 个，可以分成 2k 组，所以异或和为 0，再有 0 \oplus 1 \oplus n+1 = n，所以构造成立。
例如 n = 6 时可以构造序列为 \{a\} = \{1,2,3,4,5,7\}。
-
n \equiv 3\pmod {4} 时：
考虑构造序列 \{2,3...,n-2,n-1,n+1,n+2\}，因为除 n-1 以外，剩下的数为 4k+2 个，可以分成 2k+1 组，所以异或和为 1，再有 1 \oplus n-1 = n，所以构造成立。
例如 n = 7 时可以构造序列为 \{a\} = \{2,3,4,5,6,8,9\}。
在 n 很小时需要注意不能按照上述方式构造，否则可能存在问题。
当 n = 3 时，通过手模可知没有构造方案满足要求，所以无解。
# Code
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, T;
int main()
{
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
if(n == 1)
{
puts("1");
continue;
}
if(n == 3)
{
puts("-1");
continue;
}
if(n % 4 == 0)
{
for(int i = 1; i <= n; i++)
{
printf("%d ", i);
}
}
else if(n % 4 == 1)
{
for(int i = 2; i < n - 1; i += 2)
{
printf("%d %d ", i, i + 1);
}
printf("%d %d %d ", n, n + 1, n + 2);
}
else if(n % 4 == 3)
{
for(int i = 2; i < n - 1; i += 2)
{
printf("%d %d ", i, i + 1);
}
printf("%d %d %d ", n - 1, n + 1, n + 2);
}
else
{
for(int i = 1; i <= n - 1; i++)
{
printf("%d ", i);
}
printf("%d ", n + 1);
}
puts("");
}
return 0;
}
```