自动搬运

查看原文

来自洛谷，原作者为

	LF_Forever Guess I'm heading home now. | I wanna Zzzz

搬运于2025-08-24 22:18:18，当前版本为作者最后更新于2021-03-17 14:54:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

仔细地审视题目，将 O 看作 0，将 X 看作 1，其实可以发现题目的意思是：

枚举所有 不重复的 n 位的二进制数，产生一个排列，使得每两个相邻的数码只有 一位不同。且这个排列的首尾都是 $(0)_{10}$ 。

因为题目说会有多组解，所以我们可以考虑一种构造的方法。

首先，当 $n=1$ 时，答案为：

0
1

最后再输出一个 0 。

从 $n=2$ 开始构造。我们可以考虑：将 $n=1$ 时的答案翻转过来，拼接在它原来答案的下面，变成了这样：

0
1
1
0

这时再将前一半的数码后面加上 0，后一半的数码后面加上 1，使它们两两不相等，于是，变成了这样：

00
10
11
01

我们现在惊奇地发现：枚举出来的数码恰好满足上述的条件。这时我们应另举一个例子 $n=3$，来验证一下。

翻转拼接 $n=2$ 时的答案：

00
10
11
01
01
11
10
00

再在各个数码的末尾添上 0 或 1：

000
100
110
010
011
111
101
001

现在，我们可以发现我们的结论是正确的了！

最后，贴上代码：

#include<bits/stdc++.h>
using namespace std;
int n,mapp[70000][20],num=2;
int main()
{
	mapp[1][1]=0;mapp[2][1]=1;//储存 n=1 时的答案。
	scanf("%d",&n);
	for(int i=2;i<=n;i++){//由于每一个 i 都要用到 i-1 时的答案
		num*=2;       //所以需要算出 2 到 n 的所有答案
		for(int j=1;j<=num/2;j++){
			for(int k=1;k<i;k++)
			 mapp[num/2+j][k]=mapp[num/2-j+1][k];//翻转
		}
		for(int j=1;j<=num;j++)
		 if(j>num/2)mapp[j][i]=1;//后 num/2 位末尾为 1
		 else mapp[j][i]=0;//前 num/2 位末尾为 0
	}
	for(int i=1;i<=num;i++){
		for(int j=1;j<=n;j++)
  		 if(mapp[i][j])printf("X");//别忘记转换成 O 和 X。
		  else printf("O");
		printf("\n");
	}
	for(int i=1;i<=n;i++)printf("O");//补上最后的 0 。
	return 0;
}