d790 - 00729 - The Hamming Distance Problem

🔗 前往 ZeroJudge 原題

題目描述

題目要求輸出所有長度為 N，且 Hamming distance 為 H 的二元字串。Hamming distance 定義為兩個相同長度字串中，對應位置上不同字元的個數。本題要求生成所有滿足條件的字串，並按照字典序輸出。

解題思路

程式碼使用迴溯法來生成所有可能的二元字串，並在生成過程中檢查 Hamming distance 是否等於 H。程式碼使用一個整數陣列 ans 來表示二元字串，其中 ans[i] 為 0 或 1。程式碼使用一個迴圈來生成所有可能的二元字串，並在迴圈中檢查 Hamming distance 是否等於 H。如果 Hamming distance 等於 H，則程式碼將字串輸出。

程式碼的核心邏輯是模擬二進位加法，並在每次加法後檢查生成的字串是否滿足 Hamming distance 的條件。z 變數代表所有可能的組合數，ans 陣列儲存目前生成的二元字串。迴圈中，++ans[0] 模擬二進位加法，如果某一位的值超過 1，則進位到下一位。然後，程式碼計算字串中 1 的個數，如果 1 的個數等於 H，則輸出字串。

複雜度分析

• 時間複雜度: O(2^N)
• 空間複雜度: O(N)

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int n,a,b;
	cin >> n;
	while(n--){
		cin >> a >> b;
		int z=(1<<a);
		int ans[a]={0};
		while(z--){
			++ans[0];
			for(int i=0;i<a;++i){
				if(ans[i]>1){
					++ans[i+1];
					ans[i]=0;
				}
			}
			int c=0;
			for(int i=0;i<a;++i)
				if(ans[i])
					++c;
			if(c==b){
				for(int i=a-1;i>=0;--i)
					cout << ans[i]; 
				cout << "\n";
			}
		}
		if(n)cout << "\n";
	}
}