alan23273850 的刷題筆記
d400: A-排列組合
Tags: bitmask, permutation
出處：https://zerojudge.tw/ShowProblem?problemid=d400
提交：https://zerojudge.tw/Submissions?problemid=d400&account=allllllan123456
問題：給你一個僅由不超過 10 個小寫字母 (可能會重複) 組成的字串 $s$，代表 $s$ 內的字母需要重新排列，接著有 m 組字母對 $(ch_{i,1}, ch_{i,2})$ 表示在每個合法排列中對於每個字母對，$ch_{i,1}$ 都一定要比 $ch_{i,2}$ 先出現，注意到前面這句話並不代表 $ch_{i,2}$ 的後方不能存在任何 $ch_{i,1}$。請你按照「每個字母第一次出現在 $s$」的字典序依序印出至多前 10 組彼此不重複的排列。舉例來說，babc 的輸出依序為 bbac, bbca, …, cbba。
解法：這題的考點著重於怎麼處理字母優先順序的問題，我的作法是對於每個字母 ch 都用一個整數 before 的 bits 去記錄有哪些字母 ch2 必須出現在 ch 前面，每個 ch2 都佔了 before 的一個 bit，當我檢查當前已經選入字母的 bitmask 已經滿足 before 的每個 1-bit 的時候，我才能繼續選入 ch。至於題目限定的字典序以及字串不重複的機制可以參考其他 permutation 相關的題目例如 d436、d781。
延伸：這題的字典序蠻特別的，我原先以為要完全按照輸入字元的順序印出，舉例來說，babc 的輸出依序應為 babc, bacb, bbac, … 等，後來發現這樣子有重複字元的話會非常難實作，就想說猜猜看只根據「每個字母第一次出現在 $s$」的這個順序輸出，沒想到竟然就不小心 AC 辣！！！！！各位不妨想想看要怎麼完全按照輸入字元的順序印出，可是又不能有重複的字串，板主目前是還想不太到啦，這看起來就頗有挑戰性的 ^_^
1#include <bits/stdc++.h>
2using namespace std;
3
4int len, kind, cnt;
5char arr[11], ans[11];
6unsigned before[26], num[26];
7
8void dfs(int nowLen, unsigned appeared) {
9 if (nowLen == len) {
10 if (cnt < 10) cnt++, puts(ans);
11 return;
12 }
13 for (int i=0; i<kind && cnt<10; i++)
14 if (num[arr[i]-'a'] && // 如果必須在 arr[i] 前面出現的字元都已經出現的話
15 ((before[arr[i]-'a']&appeared) == before[arr[i]-'a'])) // 我才能選 arr[i]
16 num[arr[i]-'a']--,
17 ans[nowLen] = arr[i],
18 dfs(nowLen+1, appeared | (1<<(arr[i]-'a'))),
19 num[arr[i]-'a']++;
20}
21
22int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
23 int m, T; cin >> T;
24 while (T--) { kind = cnt = 0;
25 cin >> arr; len = strlen(arr); memset(num, 0, sizeof num);
26 for (int i=0; i<len; i++)
27 if (!num[arr[i]-'a'])
28 num[arr[i]-'a'] = 1, arr[kind++] = arr[i];
29 else num[arr[i]-'a']++;
30 cin >> m; memset(before, 0, sizeof before);
31 while (m--) {
32 char a, b; cin >> a >> b;
33 before[b-'a'] |= 1 << (a-'a');
34 }
35 dfs(0, 0);
36 if (!cnt) puts("NANJ你唬我");
37 }
38 return 0;
39}