修改 徐一笑 高阳老师班 (hetao2741064) 代码

AC请点赞

#include<bits/stdc++.h>    
using namespace std;
int main(){
    unsigned long long sum=4,n,i,x,num,sum2=1,k,j=0;
    bool biao=0,biao2=0;
    int x2;
    cin>>n>>k;
    k=k+1;//如果输入k为技术的话，后面就麻烦了。
    char s2;//用于进行字符与数字的转化。
    string s="";
    for (int i=1;i<=63;i++)
    {
        sum2=sum2*2;
    }//用于最后的特判。
    if (n==64)
    {
        biao2=1;
        n--;
    }
    if (n==63)
    {
        biao=1;
        n--;
    }//因为在我这个代码里，最前面的输在最后加，这里先用两个标记数组记录一下。
    for (i=1;i<=n;i++)
    {
        x=k%sum;//对k取余，这样就可以把前面无用的循环段剔除掉，小学奥数的，不必多讲。
        num=sum/4;//就以中间变量，长度为循环的一段。
        if (x<=num || x>num*3)//如果是循环的第1或第4段，就是0（0110参照这个）。
            x2=0;
        else
            x2=1;
        s2=x2+'0';//数字转字符。
        s=s2+s;//加入答案。
        sum=sum*2;//我们可以发现，位数往前一位，循环段长度就*2；
    }
    if (biao)
    {
        if (k%2==1)
        {
            j=0.5;
        }//因为k是整型变量，所以就用j存小数部分。
        if (k/2+j<=sum2/4 || k/2+j>sum2/4*3)
        {
            s="0"+s;
        }//判断是第一部分还是第四部分。
        else{
            s="1"+s;
        }//是第2、3部分，在答案里加入1；
    }
    j=0;
    if (biao2)
    {
        if (k-1==18446744073709551615)
        {
            cout<<"1"<<s;
            return 0;
        }//因为最开始的k+1，所以如果k=最后一个数的话，就算不对，就得用特判。
        if (k%4==0)
            j=0;
        if (k%4==1)
            j=0.25;
        if (k%4==2)
            j=0.5;
        if (k%4==3)
            j=0.75;//同上，j存储小数部分。
        if (k/4+j<=sum2/4 || k/4+j>sum2/4*3)
        {
            s="0"+s;
        }//判断是第1、4部分还是第2、3部分。
        else{
            s="1"+s;
        }
    }
    cout<<s;//输出答案。
    return 0;
}

先找规律再做题

在看代码之前，我们先要了解格雷码的一个规律：

1. 格雷码的最后一位从第一个开始分别是0110 0110 0110 0110 0110这样一直往后延。
2. 倒数第二位是00111100 00111100 00111100 00111100 00111100 这样一直往后延。
3. 倒数第三位是00001111110000 00001111110000 00001111110000 00001111110000一直往后延。

是不是发现什么了，格雷码的每一位都是遗传有规律的数字循环，这串循环着的数字，前四分之一是0，后四分之一也是0，其余是1。

• 当我们发现这个规律的时候，我们就能轻易写出类似下面这样的代码。(注：我们称循环着的数字的“前四分之一”是循环的第一段，“前四分之一到四分之二”是循环的第二段，以此类推。其中1、4段是0，2、3段是1。而如0110这样一段完整的循环我们称之为循环段)

解析在注释中（非AC）

#include
using namespace std;
int main()
{
    unsigned long long sum=4,n,k,i,x,num;
    int x2;
    cin>>n>>k;
    k=k+1;//如果输入k为技术的话，后面就麻烦了。
    char s2;//用于进行字符与数字的转化。
    string s="";//用于储存答案。
    for (i=1;i<=n;i++)
    {
        x=k%sum;//对k取余，这样就可以把前面无用的循环段剔除掉，小学奥数的，不必多讲。
        num=sum/4;//就以中间变量，长度为循环的一段。
        if (x<=num || x>num*3)//如果是循环的第1或第4段，就是0（0110参照这个）。
            x2=0;
        else
            x2=1;
        s2=x2+'0';//数字转字符。
        s=s2+s;//加入答案。
        sum=sum*2;//我们可以发现，位数往前一位，循环段长度就*2；
    }
    cout<<s;
    return 0;
}

这个代码看上去不错，没啥问题，但却只能得70分。其他则会出现这样的报错：Runtime Error 0Floating point exception 。 我们仔细看看就知道，当n大于等于63时，sum会大于2的64次方-1，所以会报错。我们有三种解决办法。

1. 最简单的，用特判，n为63或64，只有两种情况，当作特殊值判断就行了，具体方法可以把k除以2或4，再放在sum里判断是第几段，很快的。
2. 转化思想，把k除以2、4、8、16等再放到sum里判断是第几段，相对于sum来说，与sum*2、*4、*8、*16的效果是一样的，两项结合，过这题完全可以。
3. 还有就是用高精度，但这里就不过多讨论了。

下面我提供一种用第一个方法写的AC的代码，其他就你们自己当作业吧（解析在注释中）。

AC代码（求赞）

    unsigned long long sum=4,n,i,x,num,sum2=1,k,j=0;
    bool biao=0,biao2=0;
    int x2;
    cin>>n>>k;
    k=k+1;//如果输入k为技术的话，后面就麻烦了。
    char s2;//用于进行字符与数字的转化。
    string s="";
    for (int i=1;i<=63;i++)
    {
        sum2=sum2*2;
    }//用于最后的特判。
    if (n==64)
    {
        biao2=1;
        n--;
    }
    if (n==63)
    {
        biao=1;
        n--;
    }//因为在我这个代码里，最前面的输在最后加，这里先用两个标记数组记录一下。
    for (i=1;i<=n;i++)
    {
        x=k%sum;//对k取余，这样就可以把前面无用的循环段剔除掉，小学奥数的，不必多讲。
        num=sum/4;//就以中间变量，长度为循环的一段。
        if (x<=num || x>num*3)//如果是循环的第1或第4段，就是0（0110参照这个）。
            x2=0;
        else
            x2=1;
        s2=x2+'0';//数字转字符。
        s=s2+s;//加入答案。
        sum=sum*2;//我们可以发现，位数往前一位，循环段长度就*2；
    }
    if (biao)
    {
        if (k%2==1)
        {
            j=0.5;
        }//因为k是整型变量，所以就用j存小数部分。
        if (k/2+j<=sum2/4 || k/2+j>sum2/4*3)
        {
            s="0"+s;
        }//判断是第一部分还是第四部分。
        else{
            s="1"+s;
        }//是第2、3部分，在答案里加入1；
    }
    j=0;
    if (biao2)
    {
        if (k-1==18446744073709551615)
        {
            cout<<"1"<<s;
            return 0;
        }//因为最开始的k+1，所以如果k=最后一个数的话，就算不对，就得用特判。
        if (k%4==0)
            j=0;
        if (k%4==1)
            j=0.25;
        if (k%4==2)
            j=0.5;
        if (k%4==3)
            j=0.75;//同上，j存储小数部分。
        if (k/4+j<=sum2/4 || k/4+j>sum2/4*3)
        {
            s="0"+s;
        }//判断是第1、4部分还是第2、3部分。
        else{
            s="1"+s;
        }
    }
    cout<<s;//输出答案。
    return 0;