CF1009G Allowed Letters

发表于 | 阅读数

给定一个长为$n$的串，字符集$’a’…’f’$。你可以重排这个串，满足指定$m$个位置上只能放特定的字符，$m$个位置以及字符集会给出,求字典序最小的串

首先看成二分图，把$a,f$字母当作$X$,位置当成$Y$。$|Y|$连向$|X|$的边就是特定字符。

根据完美匹配可以知道，产生了$X$的子集$\leq|Y|$

二分图G中的两部分顶点组成的集合分别为X, Y(假设有$|𝑋|≤|𝑌|$)。G中有一组无公共点的边，一端恰好为组成X的点(也就是存在完美匹配)的充分必要条件是：X中的任意k个点至少与Y中的k个点相邻，即对于X中的一个点集W ，令N(W)为W的所有邻居， 霍尔定理即对于任意W，$|𝑊|≤|𝑁(𝑊)|$

$f[i][s]，表示[i,n]$,子集$s$所连的位置有多少。

那么贪心的取，判断是否可以取到由于取完了$ans[i]=j$，则$cnt[j]-1$，这时候判断$f[i+1][s]\geq cnt[j]$。根据定理即可。

比如$a \ 1 \ b$

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e5 + 10;
const int mod = 1e9 + 7;

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
char s[N], ans[N];
int cnt[N], z[N];
int f[N][70];
int st, n;
bool check(int i)
{
    for (int t = 0; t < st; t++)
    {
        int res = 0;
        for (int k = 0; k < 6; k++)
            if ((1 << k) & t)
            {
                res += cnt[k];
            }

        if (res > f[i + 1][t])
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    scanf("%s", s + 1);
    int m = read();
    n = strlen(s + 1);
    for (int i = 1; i <= n; i++)
        cnt[s[i] - 'a']++;
    for (int i = 1; i <= m; i++)
    {
        char t[10];
        int x = read();
        scanf("%s", t + 1);

        int len = strlen(t + 1);

        for (int j = 1; j <= len; j++)
        {
            z[x] |= (1 << (t[j] - 'a'));
        }
    }

    st = 1 << 6;
    for (int i = n; i >= 1; i--)
    {
        if (!z[i])
            z[i] = st - 1;
        for (int j = 0; j < st; j++)
        {
            f[i][j] = f[i + 1][j] + ((j & z[i]) > 0);
        }
    }

    for (int i = 1; i <= n; i++)
    {
        int ok = 0;
        for (int j = 0; j < 6; j++)
            if (cnt[j] > 0 && ((1 << j) & z[i]))
            {
                cnt[j]--;

                if (check(i))
                {
                    ans[i] = 'a' + j;

                    ok = 1;
                    break;
                }
                else
                    //cout << 2333 << endl;
                    cnt[j]++;
            }
        if (!ok)
        {
            return puts("Impossible"), 0;
        }
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i];
    cout << endl;
}