alan23273850 的刷題筆記
d115: 數字包牌
Tags: bitmask, permutation
出處：https://zerojudge.tw/ShowProblem?problemid=d115
提交：https://zerojudge.tw/Submissions?problemid=d115&account=allllllan123456
問題：給你 $n\le100$ 個正整數，你要從這些數字中選出 m 個號碼，然後按照數值大小的字典順序依序印出這 m 個號碼的所有排列。
解法：看到這種題目一定秒想到用 DFS，先對全部的 n 個數字由小到大排序之後再依序檢查，對每個數字優先嘗試選入，接下來才是放棄不選，每次一選滿 m 個數字之後就馬上印出，這樣就自然會是字典順序了。另外，其實也可以用一個整數的各個 bits 去記錄每個數字的選或不選，程式碼是用 unsigned 型別，代表 m 其實不超過 32。
1#include <bits/stdc++.h>
2using namespace std;
3
4int n, m, arr[100];
5
6void dfs(int index, unsigned choose) {
7 if (__builtin_popcount(choose) == m) {
8 for (int i=0; choose; i++, choose>>=1)
9 if (choose & 1)
10 cout << arr[i] << ' ';
11 cout << '\n';
12 return;
13 }
14 if (index==n) return;
15 dfs(index+1, choose | (1<<index));
16 dfs(index+1, choose);
17}
18
19int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
20 while (cin >> n && n) {
21 for (int i=0; i<n; i++) cin >> arr[i];
22 cin >> m;
23 sort(arr, arr+n);
24 dfs(0,0); cout << '\n';
25 }
26 return 0;
27}