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

沉冥Charming · 2019-11-16 18:38:06 · 题解

• 签到题，找规律即可

• 很明显，n 位格雷码有 2^n 个二进制串

• 若k在前一半，则开头是0，反之开头是1

• 直接从n循环到1模拟一下，一位一位输出就好了

#include<iostream>
#include<cstdio>
using namespace std;
#define ll unsigned long long //不开ull见祖宗
ll a[70]= {1,2,4,8,16,32,64,
           128,256,512,1024,2048,4096,
           8192,16384,32768,65536,131072,262144,
           524288,1048576,2097152,4194304,8388608,16777216,
           33554432,67108864,134217728,268435456,536870912,1073741824,
           2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,
           137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,
           8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,
           562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,
           36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,
           2305843009213693952,4611686018427387904,9223372036854775808
          }; //打个表
ll n,k;
int main()
{
    cin>>n>>k;
    for (int i=n; i>=1; i--)
    {
        ll mid=(a[i]-1)/2;
        if (k<=mid)
            putchar('0');
        else
        {
            putchar('1');
            k=a[i]-1-k; //逆序的时候需要找到k在前一个串中的位置
        }
    }
    return 0;
}

• 关于ull的问题：

• 2^64正好是0，减1变成2^64-1

• 正好够用