把原字符看成 $X$,每个位置看成 $Y$,每种字符向每个能去的位置连边,就成了一个二分图完美匹配的问题。 现要得到字典序最小,那么就枚举每一位要放什么,然后看放完这种字符,
把原字符看成 $X$,每个位置看成 $Y$,每种字符向每个能去的位置连边,就成了一个二分图完美匹配的问题。
现要得到字典序最小,那么就枚举每一位要放什么,然后看放完这种字符,剩下的字符的个数和后面能不能形成完美匹配。
根据霍尔定理,选择 $X$ 中的一个子集 $s$,和 $Y$ 连边的点集为 $N(s)$,那么 $N(s)$ 的大小就只和 $s$ 中的字符种类数有关。
当 $s$ 最大时肯定是每种字符的个数都拿上。那么就用一个 $cnt[i][s]$ 表示后缀 $[i, n]$ 中和 $s$ 连边的位置数。
然后枚举一下子集再判断一下 $N(s)$ 和 $s$ 的关系就行了。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; int cnt[N][1 << 6], cnt2[6], bin[N]; char s[N], ans[N]; int main() { scanf("%s", s + 1); int n = strlen(s + 1); for (int i = 1; i <= n; i++) cnt2[s[i] - ‘a‘]++; int m; scanf("%d", &m); for (int i = 1; i <= m; i++) { char t[10]; int x; scanf("%d%s", &x, t); for (int j = 0; t[j]; j++) bin[x] |= (1 << (t[j] - ‘a‘)); } for (int i = n; i >= 1; i--) { if (bin[i] == 0) bin[i] = (1 << 6) - 1; for (int s = 0; s < (1 << 6); s++) { cnt[i][s] = cnt[i + 1][s]; if (bin[i] & s) cnt[i][s]++; } } for (int i = 1; i <= n; i++) { bool flag = false; for (int alp = 0; alp < 6; alp++) { if (!cnt2[alp] || (bin[i] >> alp & 1) == 0) continue; cnt2[alp]--; bool check = 1; for (int s = 0; s < (1 << 6); s++) { int cn = 0; for (int j = 0; j < 6; j++) if (s >> j & 1) cn += cnt2[j]; if (cn > cnt[i + 1][s]) { check = false; break; } } if (check) { ans[i] = (char)(alp + ‘a‘); flag = 1; break; } cnt2[alp]++; } if (!flag) { puts("Impossible"); return 0; } } puts(ans + 1); return 0; }View Code