[心得] [演算法心得] Uva 729. The Hamming Distance Problem

[複製鏈接]

jimmyhealer

7 主題	0 好友	11 積分

新手上路

Rank: 1

UID: 320966
帖子: 146
主題: 7
精華: 0
積分: 11
楓幣: 756
威望: 11
存款: 0
贊助金額: 0
推廣: 0
ＧＰ: 31
閱讀權限: 10
性別: 保密
在線時間: 9 小時
註冊時間: 2021-9-30
最後登入: 2022-7-6

發消息

電梯直達

1樓

發表於 2022-5-12 11:26:55 |只看該作者 |倒序瀏覽

嗨大家好~ 我是新加入論壇的萌新，之後可能會每日更新一下演算法心得，那目前會在 c/c++ 版，如果大家很熱絡的話再申請演算法/競賽程式版吧!

--------------------------------------------------- 正文開始 ---------------------------------------------------

題目名稱: The Hamming Distance Problem
題目網站: Uva
題目網址: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=729
題目內容:

The Hamming distance between two strings of bits (binary integers) is the number of corresponding
bit positions that differ. This can be found by using XOR on corresponding bits or equivalently, by
adding corresponding bits (base 2) without a carry. For example, in the two bit strings that follow:
A 0 1 0 0 1 0 1 0 0 0
B 1 1 0 1 0 1 0 1 0 0
A XOR B = 1 0 0 1 1 1 1 1 0 0
The Hamming distance (H) between these 10-bit strings is 6, the number of 1's in the XOR string.

題目大意:

給你 N H，N 代表長度，H 代表字符串中有 H 個 1.
問你有多少種字串排列方式，並從小到大輸出。

範例輸入 #1:
1

4 2

範例輸出 #1:
0011
0101
0110
1001
1010
1100
--------------------------------------------------- 題解心得 ---------------------------------------------------

遇到全排列第一個想到使用 next_permutation() ，這是 algorithm 裡面的函式庫。
他的作用是將陣列的值找出下一個字典序排列。
而他的終止條件是逆排序 (字典序的最後一個)，所以一開始是要排序過的 (就是 0...01...1)。

AC code :

#include<bits/stdc++.h>

#define ll long long

#define INF 0x3f3f3f3f

#define MOD 1000000007

#define io iOS::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

const int MXN = 200005;

//int ar[MXN];

void sol(){

  ll ans = 0, n = 0, m = 0, k = 0;

  cin >> n >> m;

  string str = "";

  for(int i = 0; i < n - m; ++i) str += "0";

  for(int i = 0; i < m; ++i) str += "1";

  do{

cout << str << '\n';

  }while(next_permutation(str.begin(), str.end()));

}

int main(){

  //io

  int t = 1;

  cin >> t;

  while(t--){

sol();

if(t) cout << '\n';

  }

}
複製代碼