企业官网建设流程全解析

题目描述

给定两个等长的二进制字符串，它们的汉明距离定义为对应位置不同的位数。要求输出所有长度为NNN、且与全零字符串汉明距离为HHH的二进制字符串，即恰好包含HHH个1和N−HN-HN−H个0的所有排列。输出按字典序升序排列。数据组数不定，每组数据之间输出空行。

输入格式

第一行包含一个整数，表示数据组数。随后每组数据占一行，包含两个整数NNN和HHH（1≤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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases,N,H;cin>>cases;for(intc=1;c<=cases;c++){if(c>1)cout<<'\n';cin>>N>>H;string hamming=string(N-H,'0')+string(H,'1');do{cout<<hamming<<'\n';}while(next_permutation(hamming.begin(),hamming.end()));}return0;}

总结

本题利用next_permutation\texttt{next\_permutation}next_permutation直接生成所有含固定数量1的二进制串，按字典序输出。核心在于初始化为最小字典序串（所有0在前，1在后），后续排列自动按序递增。该方法代码简洁，效率高，是处理组合生成问题的常用手段。注意每组数据间输出空行，以避免格式错误。