自动搬运

查看原文

来自洛谷，原作者为

	youyou2007 如果你已选择生命，那便是选择了活下去。 活在这个世界，见证这个世界。体验它，并真切地接受这最后的每一个当下。

搬运于2025-08-24 22:50:18，当前版本为作者最后更新于2023-08-23 23:45:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里是出题人题解。

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$。

• 性质 $2$：如果 $a$ 为正整数，那么 $a \oplus a = 0$，$a \oplus 0 = a$。

• 性质 $3$：由第一个性质还可以得出，如果 $a$ 是偶数，那么有 $a \oplus 1 = a + 1$ ，如果 $a$ 是奇数，那么有 $a \oplus 1 = a-1$。

明确了上述性质，我们很快会有一个想法：可以考虑将一个偶数与比该偶数多 $1$ 的奇数视为一组，这样每一组的异或和为 $1$。而每两组的异或和为 $0$。

即，当 $a$ 是偶数时，$a \oplus (a+1)=1$，$a \oplus (a+1) \oplus (a+2)\oplus (a+3)=0$。

发现两组是 $4$ 个数，根据 $n \% 4$ 的余数进行分类讨论构造：

• $n \equiv 0\pmod {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\}$。

• $n \equiv 1\pmod {4}$ 时：

考虑构造序列 $\{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\}$。

• $n \equiv 2\pmod {4}$ 时：

考虑构造序列 $\{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 \le 3$ 时）

在 $n$ 很小时需要注意不能按照上述方式构造，否则可能存在问题。

当 $n = 3$ 时，通过手模可知没有构造方案满足要求，所以无解。

$n=2$ 与 $n=1$ 在样例中已经给出一组可行解，因此不再赘述。

Code

#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; 
}