https://ac.nowcoder.com/acm/contest/327/E

C++版本一

std

题解：

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[2000000];
int b[2000000];
 
int ones(int x)
{
    int ans=0;
    while (x)
    {
        ans++;
        x=x&(x-1);
    }
    return ans;
}
 
 
 
int main()
{
    //freopen(".\\data\\1.in","r",stdin);
    //freopen(".\\data\\1.out","w",stdout);
    scanf("%d%d",&n,&m);
    if (m%2==0)
    {
        printf("NO\n");
        return 0;
    }
    a[0]=0;
    a[1]=1;
    for (int i=1;i<n;i++)
    {
        for (int j=(1<<i);j<(1<<(i+1));j++)
        {
            a[j]=(1<<i)^(a[(1<<(i+1))-1-j]);
        }
    }
    if (m==1)
    {
        printf("YES\n");
        for (int i=0;i<(1<<n);i++)
        {
            printf("%d\n",a[i]);
        }
    }
    else
    {
        printf("YES\n");
        for (int i=0;i<(1<<(m+1));i++)
        {
            if (i%2==0) b[i]=a[i];
            else b[i]=a[i]^((1<<(m+1))-1);
        }
        for (int i=m+1;i<n;i++)
        {
            int p=-1;
            for (int j=0;j<(1<<i);j++)
            {
                if (ones(b[j]^b[(1<<i)-1])==m-1 && ones(b[(j+(1<<i)-1)%(1<<i)])==m-1)
                {
                    p=j;
                    break;
                }
            }
            assert(p!=-1);
            for (int j=0;j<(1<<i);j++)
            {
                b[(1<<i)+j]=(1<<i)^b[(p+j)%(1<<i)];
            }
        }
        for (int i=0;i<(1<<n);i++)
        {
            printf("%d\n",b[i]);
        }
    }
    return 0;
}

扫一扫，把题目装进口袋