题解 P6065 [USACO05JAN]Sumsets S

· · 题解

仔细地审视题目，将 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;
}