蓝桥杯C/C++国赛冲刺打卡4/30

• 1 格雷码
• • • 洛谷题目链接
• 2 思路

这一道题是一道找规律题，下面我们举例当n为3时候的格雷码。

• 首先，我们观察题目中的一组处理好的串：3 位格雷码为：000，001，011，010，110，111，101，100，编号从 0∼7
• 在这里，我们发现，前四个串的第一位为0（000，001，011，010），后四个串第一位数都是1（110，111，101，100）然后我们从中间分开，前四个串放一起，后四个串放一起，又会发现
• 在这前四个串中（即前半部分），前两个串的第二位都是0（000，001）设这组串为a，后两个串的第二位都是1（011，010）设这组串为b，二分a（000，001），前一个串的第三位都是0 (即前半部分)，后一个串的第三位都是1 (即后半部分)，二分b（011，010），前一个串的第三位都是1 (即前半部分)，后一个串的第三位都是0 (即后半部分)
• 在后四个串中（即后半部分），前两个串的第二位都是1（110，111）设这组串为c，后两个串的第二位都是0（101，100）设这组串为d，二分c（110，111），前一个串的第三位是0 (即前半部分)，后一个串的第三位是1 (即后半部分)，二分d（101，100），前一个串的第三位是1 (即前半部分)，后一个串的第三位是0 (即后半部分)
• 然后我们理一下思路，就会发现一个规律，每一个阶段，前半段或后半段二分次数对应的位数是0还是1，取决于上一个阶段，也就是看k在上一个阶段，是在前半段，还是后半段，来自前半段的话，前半段对应位数的字符则是0，后半段是1，来自后半段的话，前半段对应位数的字符则是1，后半段是0

c++代码：

#include
#include
#include

using namespace std;

typedef unsigned long long ll;
ll n,k,tmp=0;
bool flag=false;

int main()
{
    cin>>n>>k;
    tmp=pow(2,n-1);
    while(tmp)//直到长度为0
    {
        if(!flag)
        {
            if(k>=tmp)
            {
                cout<<"1";
                k-=tmp;
                flag=true;
            }
            else
            {
                cout<<'0';
                flag=false;
            }
        }
        else
        {
            if(k>=tmp)
            {
                cout<<'0';
                flag=true;
                k-=tmp;
            }
            else
            {
                cout<<'1';
                flag=false;
            }
        }
        tmp/=2;//每次去掉一半，k在前半段则去掉后半段长度，在后半段则去掉前半段长度
    }
    return 0;
}