题解 P1461 【海明码 Hamming Codes】

ylsoi · 2017-08-17 13:53:09 · 题解

这个题目真的有一点意思，本来看不懂题目，后面就突然明白了只是求几个N个二进制数，然后要求二进制数两两之间不同的位数必须要大于等于D，然后如果有多组解法的话就取小的那个。但是这里我要隆重的介绍一个函数__builtin_popcount()它可以统计这个数转化为二进制数中一的个数，我们只要亦或一下，再调用这个神奇的函数，就过了。。。。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=70;
int n,b,d,ans[maxn],len;
int main()
{
    scanf("%d%d%d",&n,&b,&d);
    len++;
    ans[len]=0;
    int i=1;
    while(len<n)
    {
        bool flag=false;
        for(int j=len;j>=1;j--)
        if(__builtin_popcount(ans[j]^i)<d)//和之前的每一个数都要比较
        {
            flag=true;
            break;
        }
        if(!flag)
        {
            len++;
            ans[len]=i;
        }
        i++;
    }
    for(i=1;i<=len;i++)
    {
        printf("%d ",ans[i]);
        if(i%10==0)cout<<endl;
    }
    return 0;
}