USACO 1363. 汉明码

AcWing网站原题通道

1363. 汉明码

题意分析：
这道题让我们求出从0开始到2^b之间的两两之间的汉明距离不小于d的n个数。
数据范围：b最大是8，那么2⁸最大也就是256，那么我们枚举出来所有的汉明距离不小于d并且小于2⁸的数，在这些点之间连上边，假设使用path数组来存储结果，因为0一定符合条件，所以直接从1开始暴搜，搜索到每个数判断这个数和已经加入到path数组中的点的汉明距离是否符合条件，如果符合条件，再加入到path数组中去。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 256;

int path[N];
bool g[N][N];
int n , b , d;

int get_ones(int x) // 获取x的二进制下的1的个数
{
    int s = 0;
    while(x)
    {
        s += x & 1;
        x >>= 1;
    }
    return s;
}

bool dfs(int u , int start)
{
    if(u == n)
    {
        for(int i = 0; i < n; i++)
        {
            cout << path[i];
            if((i + 1) % 10) cout << ' ';
            else cout << endl;
        }
        return true;;
    }
    
    for(int i = start; i < 1 << b; i++) // 从start开始枚举
    {
        bool flag = true; // 标记当前这个数是否和已经在路径中的数的汉明距离符合条件       
        for(int j = 0; j < u; j++) 
            if(!g[i][path[j]])
                flag = false;
                
        if(flag) // 如果符合条件
        {
            path[u] = i; // 记录当前数
            if(dfs(u + 1 , i + 1)) return true; // 枚举下一个数
        }
    }
    return false;
}

int main()
{
    cin >> n >> b >> d;
    for(int i = 0; i < 1 << b; i++)
        for(int j = 0; j < 1 << b; j++)
            if(get_ones(i ^ j) >= d)
                g[i][j] = true; // g[i][j]为true表示i和j这两个点的汉明距离不小于d

    dfs(1 , 1); // 因为 0 这个数一定符合标准，所以从1开始枚举
    
    return 0;
}

最后

以上就是动听火为你收集整理的USACO 1363. 汉明码的全部内容，希望文章能够帮你解决USACO 1363. 汉明码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。