题目描述给定两个等长的二进制字符串它们的汉明距离定义为对应位置不同的位数。要求输出所有长度为NNN、且与全零字符串汉明距离为HHH的二进制字符串即恰好包含HHH个1和N−HN-HN−H个0的所有排列。输出按字典序升序排列。数据组数不定每组数据之间输出空行。输入格式第一行包含一个整数表示数据组数。随后每组数据占一行包含两个整数NNN和HHH1≤H≤N≤161 \le H \le N \le 161≤H≤N≤16。数据组之间可能有一个空行但输入读取通常忽略空白。输出格式对于每组数据输出所有满足条件的二进制字符串每行一个按字典序升序。每组数据的输出之间用一个空行分隔。样例输入1 4 2样例输出0011 0101 0110 1001 1010 1100题目分析问题等价于生成所有含HHH个1和N−HN-HN−H个0的NNN位二进制串并按字典序升序输出。由于N≤16N \le 16N≤16总组合数最多为C(16,8)12870C(16,8) 12870C(16,8)12870数量较小可直接生成所有排列并排序。标准库函数next_permutation\texttt{next\_permutation}next_permutation能够按字典序生成下一个排列前提是初始序列为字典序最小的排列。将字符串初始化为N−HN-HN−H个0后跟HHH个1即得到所有排列中的最小字典序串然后不断调用next_permutation\texttt{next\_permutation}next_permutation即可按序输出全部。解题思路对于每组输入NNN和HHH步骤1\texttt{1}1. 构造初始字符串sss由N−HN-HN−H个0和HHH个1组成形如00...011...1这是所有满足条件的串中字典序最小的。步骤2\texttt{2}2. 使用do-while循环首先输出当前串然后调用next_permutation(s.begin(),s.end())\texttt{next\_permutation}(s.begin(), s.end())next_permutation(s.begin(),s.end())生成下一个字典序更大的排列直到没有下一个排列为止。步骤3\texttt{3}3. 每组输出后若还有后续组则输出一个空行。算法时间复杂度为O(C(N,H)×N)O(C(N,H) \times N)O(C(N,H)×N)空间复杂度O(N)O(N)O(N)完全满足N≤16N \le 16N≤16的限制。代码实现// The Hamming Distance Problem// UVa ID: 729// Verdict: Accepted// Submission Date: 2016-11-29// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases,N,H;cincases;for(intc1;ccases;c){if(c1)cout\n;cinNH;string hammingstring(N-H,0)string(H,1);do{couthamming\n;}while(next_permutation(hamming.begin(),hamming.end()));}return0;}总结本题利用next_permutation\texttt{next\_permutation}next_permutation直接生成所有含固定数量1的二进制串按字典序输出。核心在于初始化为最小字典序串所有0在前1在后后续排列自动按序递增。该方法代码简洁效率高是处理组合生成问题的常用手段。注意每组数据间输出空行以避免格式错误。