Educational Codeforces Round 47 G. Allowed Letters

G. Allowed Letters

題意：給一個長度為 n n n的字元串，字元串元素範圍為 a a a到 f f f，有 m m m個限制條件，每個條件限制了某位置隻能填指定元素，你要給字元串重新排列，求排列後字典序最小的字元串。

解法：不妨把重排的字元串看成二分圖的左邊集合，原字元串看成二分圖的右邊集合，我們來給它們進行字典序最小的二分圖最大比對，我們可以從前往後枚舉每個位置填的最小字元，然後用 h a l l hall hall定理去 c h e c k check check，設 c n t [ s ] cnt[s] cnt[s]為原字元串集合為 s s s時包含了多少個元素，設 v a l [ i ] val[i] val[i]為第 i i i個位置能填的字元集合，設 d [ i ] [ s ] d[i][s] d[i][s]為 i − n i-n i−n的位置 s s s或 s s s的子集包含了多少個 v a l [ j ] val[j] val[j]，每次我們枚舉 i i i位置上填的字元 j j j，當所有的集合 s s s都滿足 c n t [ s ] − ( s > > j & 1 ) = d [ i + 1 ] [ s ] cnt[s]-(s>>j\&1)=d[i+1][s] cnt[s]−(s>>j&1)=d[i+1][s]時才能去填 j j j，那麼這題就寫完了

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
char s[maxn];
int cnt[1 << 6], d[maxn][1 << 6], val[maxn];
int main()
{
    int n, m, x;
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < 1 << 6; j++)
            if (j >> (s[i] - 'a') & 1)
                cnt[j]++;
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%s", &x, s + 1);
        for (int j = 1; s[j]; j++)
            val[x] |= 1 << s[j] - 'a';
    }
    for (int i = n; i; i--)
    {
        if (!val[i])
            val[i] = (1 << 6) - 1;
        for (int j = 1; j < 1 << 6; j++)
        {
            d[i][j] = d[i + 1][j];
            if ((j & val[i]) == val[i])
                d[i][j]++;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        int ok = 0;
        for (int j = 0; j < 6; j++)
            if (val[i] >> j & 1)
            {
                int okk = 1;
                for (int k = 1; (k < 1 << 6) && okk; k++)
                    if (cnt[k] - ((k >> j) & 1) < d[i + 1][k])
                        okk = 0;
                if (okk)
                {
                    s[i] = j + 'a';
                    ok = 1;
                    for (int k = 1; k < 1 << 6; k++)
                        if (k >> j & 1)
                            cnt[k]--;
                    break;
                }
            }
        if (!ok)
            return puts("Impossible"), 0;
    }
    s[n + 1] = '\0';
    puts(s + 1);
}