题解 P5657 【格雷码【民间数据】】

· · 题解

这一题

就是找规律 形式上有点像二分

考场上想复杂了以为和位运算有关

结果在错误的路上一去不复兮

回去才发现

这就是一个找规律题 ....

首先

我们观察题目给的一组处理好的串(我们称每一个经处理后的格雷数为串)

000，001，011，010，110，111，101，100，

会惊奇地发现

前四个串第一位数都为0

（000，001，011，010） 数字的加粗好像不是很明显

后四个串第一位数都是1

（110，111，101，100）

然后我们从中间分开

前四个串放一起

后四个串放一起

继续看

又会惊奇地发现

1. 在这前四个串中（即前半部分）

前两个串的第二位都是0（000，001）设这组串为a

后两个串的第二位都是1（011，010）设这组串为b

2. 在后四个串中（即后半部分）

前两个串的第二位都是1（110，111）设这组串为c

后两个串的第二位都是0（101，100）设这组串为d

然后

我们理一下思路

就会发现一个规律

每一个阶段

前半段或后半段二分次数对应的位数是0还是1

取决于上一个阶段

也就是看k在上一个阶段
是在前半段
还是后半段

来自前半段的话

可以在处理的过程中直接输出

不需要存

还有一点！！

一定要用unsigned long long !!!!!

下面给出代码

#include <cstdio>
#include <iostream>
#include <cmath>

using namespace std;

unsigned long long k,bk;
int n;
bool flag;

int main(){

    cin>>n>>k;
    bk=pow(2,n-1);//从0开始编号则n-1

    while(bk){ //直到长度为0

        if(!flag){
            if(k < bk) cout<<"0";//此处省略一个flag=false;
            else if(k >= bk) {
                cout<<"1";
                k -= bk;//为下一阶段判断k的位置做准备
                flag = true;//k在后半段下一阶段为10顺序

            }
        }

        else if(flag){
           if(k < bk){
                cout<<"1";
                flag = false;//若k在前半段，使下一阶段为01顺序
            } 
            else if(k >= bk) { //如果k大于bk则在后半段
                cout<<"0";
                k -= bk;//为下一阶段判断k的位置做准备
                                        //此处省略一个flag=true;
            }
        }

        bk >>= 1;//每次去掉一半，k在前半段则去掉后半段长度，
                                          在后半段则去掉前半段长度

    }

    return 0;
}

来自一位考场爆零的蒻苣