题解：洛谷 P1461 [USACO2.1] 海明码 Hamming Codes-北京尧图网络

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1461 [USACO2.1] 海明码 Hamming Codes - 洛谷【题目描述】给出n,b,d要求找出n个由 0,10,1 组成的编码每个编码有b位使得两两编码之间至少有d个单位的 “Hamming距离”。“Hamming距离”是指对于两个编码他们二进制表示法中的不同二进制位的数目。看下面的两个编码0x554和0x234十六进制数0x554 0101 0101 0100 0x234 0010 0011 0100 不同位 xxx xx因为有五个位不同所以“Hamming距离”是 5。【输入】一行包括n,b,d。【输出】n个编码用十进制表示要排序十个一行。如果有多解你的程序要输出这样的解假如把它化为 2^b进制数它的值要最小。【输入样例】16 7 3【输出样例】0 7 25 30 42 45 51 52 75 76 82 85 97 102 120 127【核心思想】问题分析给定n , b , d n, b, dn,b,d要求找出n nn个b bb位二进制编码0 ∼ 2 b − 1 0 \sim 2^b-10∼2b−1使得任意两个编码的汉明距离≥ d \ge d≥d。输出按十进制升序排列十个一行。若有多解要求化为2 b 2^b2b进制时值最小即十进制值最小。算法选择贪心构造从小到大枚举候选数每次选择第一个与已选所有数汉明距离均≥ d \ge d≥d的数位运算计算汉明距离逐位比较两个数的二进制位统计不同位的数量关键步骤读入n nn编码数量、b bb位数、d dd最小汉明距离贪心构造编码i ii从1 11到n nn枚举候选数j jj从0 00到2 b − 1 2^b-12b−1对当前候选j jj遍历已选编码a [ 1.. i − 1 ] a[1..i-1]a[1..i−1]计算hamming(a[k], j, b)若存在 d dd的标记flag 1并跳出若flag 0与所有已选编码距离均≥ d \ge d≥da[i] j跳出内层循环继续构造下一个编码输出按十个一行的格式输出所有编码时间/空间复杂度时间复杂度O ( n ⋅ 2 b ⋅ n ⋅ b ) O ( n 2 ⋅ b ⋅ 2 b ) O(n \cdot 2^b \cdot n \cdot b) O(n^2 \cdot b \cdot 2^b)O(n⋅2b⋅n⋅b)O(n2⋅b⋅2b)实际因贪心提前终止远小于理论值空间复杂度O ( n ) O(n)O(n)存储选中的编码贪心构造的核心思想从小到大枚举保证最小性从0 00开始依次尝试候选数第一个满足条件的数必然是最小的从而保证最终序列字典序最小汉明距离逐位计算利用位运算1取最低位1右移逐位比较统计不同位数增量式验证新候选只需与已选编码比较无需考虑未选编码贪心最优性该问题中贪心策略能得到最优解因为编码空间足够大2 b 2^b2b且从小到大选择不会阻塞后续选择适用于编码构造、距离约束、贪心选择类问题【解题思路】【算法标签】#普及 #位运算【代码详解】#includebits/stdc.husingnamespacestd;intn,b,d,a[70];inthamming(intx,inty,intb){intcnt0;// 定义计数器for(inti1;ib;i){intxxx1,yyy1;// 比较最后一位如711,911if(xx!yy)cnt;// 如果最后一位不相同则不同数量加1x1;// xx和yy都向右移一位下轮仍然做最后一位的比较y1;}// cout cnt cnt endl;returncnt;// 返回所有位比较后不相同的位数}intmain(){cinnbd;// 输入n、b和dfor(inti1;in;i){// 要找到n个数for(intj0;j1(b1)-1;j){// 数在0到1b的范围内如b7数的范围为0-255intflag0;// 定义标记for(intk1;ki;k){// 题目要求与其他所有的数相比if(hamming(a[k],j,b)d){// 只要遇到一个不符合要求的flag1;// 修改标记位break;// 退出循环}}if(!flag){// 如果都满足要求a[i]j;// 将j这个数赋值给a[i]break;// 退出循环继续下轮查找}}}for(inti1;in;i){// 遍历a数组中的所有数couta[i] ;// 依次输出if(i%100)coutendl;// 遇到i为10的倍数就输出换行}coutendl;return0;}【运行结果】16 7 3 0 7 25 30 42 45 51 52 75 76 82 85 97 102 120 127

题解：洛谷 P1461 [USACO2.1] 海明码 Hamming Codes

相关推荐

英飞凌一站式智能家居方案：从MCU选型到场景联动的技术拆解

题解：洛谷 P1467 [USACO2.2] 循环数 Runaround Numbers

我让AI读数据手册，它读完开始一本正经地瞎编

更多资讯

JJencode编码解密工具：前端JS代码混淆与源码还原实操

OpenClaw与LINE集成提升养虾业沟通效率

Java record 规范构造器能否被反序列化或反射绕过

Unity Package Manager刷新错误排查与解决方案

淘宝商品详情API开发实战与性能优化指南

MIUI 11老机型：TWRP永久固定与无密data分区实战

今日更新

淘宝商品详情API开发实战与性能优化指南

Unity Package Manager刷新错误排查与解决方案

Java record 规范构造器能否被反序列化或反射绕过

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？