P1461 海明码 Hamming Codes网页链接P1461 海明码 Hamming Codes题目描述给出n , b , d n,b,dn,b,d要求找出n nn个由0 , 1 0,10,1组成的编码每个编码有b bb位使得两两编码之间至少有d dd个单位的Hamming 距离。Hamming 距离是指两个二进制编码中的不同二进制位的数目。例如编码0101 0101 0100和0010 0011 0100之间的Hamming 距离是5 550101 0101 0100 0010 0011 0100 ^^^ ^^输入格式一行三个整数n , b , d n,b,dn,b,d。输出格式输出字典序最小的解n nn个编码同样也要升序输出每输出10 1010个编码换一行。你需要先将每个编码当成二进制数再将其转成十进制数输出。输入输出样例 #1输入 #116 7 3输出 #10 7 25 30 42 45 51 52 75 76 82 85 97 102 120 127说明/提示对于100 % 100\%100%的数据1 ≤ n ≤ 64 1\le n \le 641≤n≤641 ≤ b ≤ 8 1\le b \le 81≤b≤81 ≤ d ≤ 7 1\le d \le 71≤d≤7。请注意题目中只要求 Hamming 距离至少为d \bm dd因此也可以大于d \bm dd。USACO 2.1翻译来自NOCOW解题思路本题是贪心枚举 海明距离计算的构造题利用数据规模小的特点通过从小到大贪心选取合法编码在满足海明距离约束的同时保证字典序最小。1. 海明距离计算两个二进制编码的海明距离等于它们按位异或结果中二进制1的个数异或操作会将不同的位标记为1、相同的位标记为0统计结果中1的数量即可得到不同位的总数。2. 贪心构造字典序最小序列要得到字典序最小的编码集合最优策略是从小到大枚举数值逐个选取合法编码初始第一个编码固定为0最小的b位二进制数保证字典序起点最优。从当前最大已选编码的下一个数开始枚举对每个候选数校验它与所有已选编码的海明距离是否都≥d。第一个满足条件的候选数就是当前最优选择将其加入结果集重复此过程直到选满n个编码。该贪心策略的正确性每一步都选择最小的可行值能保证整体序列的字典序最小。3. 复杂度分析b最大为8候选数总数仅2 8 256 2^825628256个n最大为64每次校验最多对比64个已选编码。总运算量为万级完全在1秒时间限制内。4. 输出格式处理最终结果天然为升序排列按题目要求每输出10个编码换一行不足10个则行尾保留空格分隔。总结核心逻辑通过异或统计1的个数计算海明距离从小到大贪心枚举选取合法编码得到字典序最小的满足距离要求的编码集合。关键操作海明距离位运算计算、升序贪心选取、全量合法性校验、按格式换行输出。效率保障候选总数仅256个暴力校验无性能压力实现简单且不易出错。代码简要说明海明距离函数hamming接收两个整数返回它们的海明距离。先对两数按位异或再循环统计结果中二进制1的位数。变量定义v数组存储选中的编码cnt记录已选编码数量初始第一个编码为0lim 1 b为候选数的上界b位二进制最大为 lim-1。枚举选码从当前最后一个编码的下一个值开始遍历候选数先快速校验与最近一个编码的距离再逐一校验所有已选编码全部满足条件则加入结果集选满n个立即终止循环。格式化输出遍历结果数组逐个数输出每满10个输出换行未满10个则输出空格分隔。输入输出使用scanf/printf保证读写效率适配小规模数据的输入输出需求。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;llhamming(ll x,ll y){ll sx^y,c0;while(s){c(s1);s1;}returnc;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,b,d;scanf(%lld%lld%lld,n,b,d);ll v[70],cnt1;v[1]0;ll lim(1LLb);for(ll iv[cnt]1;ilim;i){if(hamming(v[cnt],i)d){boolflg1;for(ll j1;jcnt;j)if(hamming(v[j],i)d){flg0;break;}if(flg){v[cnt]i;if(cntn)break;}}}for(ll i1;in;i){printf(%lld,v[i]);if(i%10)printf( );elseprintf(\n);}return0;}