[BZOJ1081]&&[SCOI2005] 超级格雷码

2014-12-26
竞赛题解 / 搜索
BZOJSCOI

描述 Description

著名的格雷码是指 2n 个不同 n 位二进制数（即 0~2n-1，不足 n 位在前补零）的一个排列，这个排列满足相邻的两个二进制数的 n 位数字中最多只有一个数字不同（例如 003 和 001 就有一个数位不同，而 003 和 030 有两个数位不同，不符合条件）。例如 n=2 时，(00,01,11,10) 就是一个满足条件的格雷码。 所谓超级格雷码就是指 Bn 个不同的 n 位 B 进制数的排列满足上面的条件。 任务：给出 n 和 B（2≤B≤36, 1≤Bn≤65535），求一个满足条件的格雷码。对于大于 9 的数位用 A~Z 表示（10~35）。

输入格式 InputFormat

只有一行，为两个整数 n 和 B。

输出格式 OutputFormat

一共 Bn 个行，每行一个 B 进制数，表示你所求得的符合条件的排列

样例输入 SampleInput

2 2

样例输出 SampleOutput

00
01
11
10

BZOJ 1081

按照规律找即可。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=25;
int i,j,t,n,m,l,r,k,z,y,x;
int b;
int a[maxn];
inline void output()
{
    int i,j,t;
    for (i=1;i<=n;i++)
    {
        if (a[i]<=9) putchar(a[i]+'0');
        else putchar(a[i]-10+'A');
    }
    putchar('\n');
}
void find(int s,int x)
{
    int i,j,t;
    if (s==0) 
    {
        output();
        return ;
    }
    if (!x)
    {
        for (i=0;i<b;i++) 
        {
            a[s]=i;
            if (i&1) find(s-1,x^1);
            else find(s-1,x);
        }
    }
    else
    {
        for (i=b-1;i>=0;i--)
        {
            a[s]=i;
            if (i&1) find(s-1,x^1);
            else find(s-1,x);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&b);
    find(n,0);
}