alan23273850 的刷題筆記
a524: 手機之謎
Tags: bitmask, permutation
出處：https://zerojudge.tw/ShowProblem?problemid=a524
提交：https://zerojudge.tw/Submissions?problemid=a524&account=allllllan123456
問題：給你一個正整數 $n\le8$，請你按照反向的字典順序輸出 1 到 $n$ 的所有可能排列。
解法：就單純的 DFS，再搭配 bitmask 記錄哪些數字已經在前面用過了即可。
1#include <bits/stdc++.h>
2using namespace std;
3
4int n;
5char ans[8];
6unsigned used;
7
8void dfs(int nowLen) {
9 if (nowLen == n) {
10 for (int i=0; i<n; i++) putchar(ans[i]);
11 putchar('\n');
12 }
13 for (int i=0; i<n; i++)
14 if (!((used >> i) & 1))
15 used |= 1 << i,
16 ans[nowLen] = '0' + n-i,
17 dfs(nowLen + 1),
18 used &= ~(1 << i);
19}
20
21int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
22 while (cin >> n) dfs(0);
23 return 0;
24}