题意
给你一个长为 (n) 的串，字符集为 (a,b,c,d,e,f) 。你可以将整个串打乱之后重新放置，但是某些位置上有一些限制：必须放某个字符集的字符。问字典序最小的串，如果无解输出 "Impossible"。
(nle 10^5)
分析
-
每次贪心地选择字典序最小的字符判断，判断后面是否可以完美匹配。可以考虑霍尔定理。
-
这里有两种想法，一种是对于每种字符开一个 (bitset) 记录被包含的位置然后求并集(字符匹配位置)；另一种则是考虑 "非完美算法" : 枚举一个字符集作为某些位置的字符集的并集，然后将所有可选字符集被完全包含的位置数量作为答案(位置匹配字符)。
-
容易发现第二种做法虽然可能求单个答案并不准确，但一定能够保证最终的答案是正确的，因为如果我们枚举的并集比实际那些位置字符集的并集要大的话，会更容易满足 $|X|le |digamma(X)| $ ，一定不会比实际的并集影响大。
-
因为要递推，所以考虑第二种方式。令 (cnt(i)(S)) 表示以 (i) 结尾的后缀中，字符集是 (S) 的子集的位置个数，如果有完美匹配则需要满足对于任意的 (S) 有： (sumlimits_{cin S}num(c)ge cnt(i+1)(S)) ，其中 (num(c)) 表示剩余 (c) 字符的个数。
-
总时间复杂度为 (O(6n imes 2^6))。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define pb push_back
#define re(x) memset(x, 0, sizeof x)
inline int gi() {
int x = 0,f = 1;
char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
return x * f;
}
template <typename T> inline void Max(T &a, T b){if(a < b) a = b;}
template <typename T> inline void Min(T &a, T b){if(a > b) a = b;}
const int N = 1e5 + 7;
int n, m;
int cnt[N][1 << 6], val[N], num[6], ans[N];
char s[N], s2[N];
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
rep(i, 1, n) num[s[i] - 'a'] ++;
m = gi();
rep(i, 1, m) {
int x = gi();
scanf("%s", s2 + 1);
int len = strlen(s2 + 1);
rep(j, 1, len) val[x] |= (1 << s2[j] - 'a');
}
for(int i = n; i; --i) {
if(!val[i]) val[i] = (1 << 6) - 1;
for(int j = 0; j < 1 << 6; ++j) {
cnt[i][j] = cnt[i + 1][j];
if((j & val[i]) == val[i]) cnt[i][j] ++;
}
}
rep(i, 1, n) {
for(int j = 0; j < 6; ++j) if(cnt[j] && val[i] >> j & 1){
num[j]--;bool fg = 1;
for(int S = 0; S < 1 << 6; ++S) {
int c = 0;
for(int k = 0; k < 6; ++k) if(S >> k & 1) c += num[k];
if(c < cnt[i + 1][S]) fg = 0;
}
if(fg) {ans[i] = j; goto A;}
num[j]++;
}
return puts("Impossible"), 0;
A:;
}
rep(i, 1, n) printf("%c", ans[i] + 'a');
puts("");
return 0;
}