P2328 [SCOI2005]超级格雷码 题解

· · 题解

嗯……我有一个神奇的思路

大致写一下……你会发现其实你每次修改的位置跟 B 进制数修改的位置不谋而合……什么意思呢……

//设输入为3 3
000  000
001  001
002  002
012  010
011  011
010  012
020  020
021  021
022  022
122  100
121  101
120  102
110  110
111  111
112  112
102  120
101  121
100  122
200  200
201  201
202  202
212  210
211  211
210  212
220  220
221  221
222  222
//左边题目所求 右边三进制的遍历

显而易见，每次三进制数变化的最高位（比如三进制数从 122 变到 200 ，则最高位为从右往左数第三位。）恰巧就是超级格雷码发生变动的位置（此时超级格雷码的第三位从 1 变成了 2 ），而变动为 ±1 ，每一位的变动方向不改变，直到触碰到 0 或是 B-1 ，那么这时候将方向变一下即可。

其实可以类比时针分针秒针的关系来理解。最高位是时针，第二位是分针，第三位是秒针。在每一小时内，分针都动了 60 下，而每一分钟内，秒针都动了 60 下。（在这里就是分别为 3 下）在这道题中，不过是可以想象成时分秒针在转过一圈后，都会反向进行旋转，这样就能保证每次操作之间的差距为 1 。

那么代码 不就呼之欲出了吗

开一个方向数组。初始设置成正增长，即从 0 到 B-1 方向的。然后去随随便便写个 n 进制加一算法，记录下进位到了哪一位，将这一位加上方向变量再输出就好啦！

以下是代码楼：

#include<bits/stdc++.h>
using namespace std;
int n,B,a[20]={0},fx[20]={0},b[20]={0};//fx就是方向数组，b是n进制遍历数组，a是输出数组
void sc(int x)//输出函数 
{
    if(x>=10)
    {
        char c=char('A'+x-10);
        printf("%c",c);
    }
    else
    {
        printf("%d",x);
    }
}
int main(){
    int times=1;//统计输出次数
    cin>>n>>B;
    for(int i=1;i<=n;i++)
        sc(a[i]);
    printf("\n");//先输出一堆0
    for(int i=0;i<=19;i++)
        fx[i]=1; 
    while(times<pow(B,n))
    {
        b[n]++;
        int flag=n;
        for(int i=n;i>=1;i--)
        {
            if(b[i]==B)
            {
                b[i]=0;
                b[i-1]++;
                flag=i-1;//记录进位到了哪里
            }
            else break;
        }
        a[flag]+=fx[flag];
        if(a[flag]==0||a[flag]==B-1)
        {
            fx[flag]=-fx[flag];
        }
        times++;
        for(int i=1;i<=n;i++)
            sc(a[i]);
        printf("\n");
    }
    return 0;
}

首篇题解！还望支持！