Allowed Letters（贪心+霍尔定理）

题意：

给定一个字符串，给出个条件，每个条件要求位置只能填某些指定的字符。要求输出满足条件且字典序最小的，否则输出。保证字符只包含

题解：

首先可以想到可以用最大流解决，从源点向个位置依次连一条流量为的边，在对个条件，每个向对应的几个字符都连一条流量为的边，最终个字符都向汇点连一条的边，最终只需要跑一遍最大流判断最大流是否为即可。这样确实可以判断当前字符串是否满足条件，但是考虑到最坏情况要跑次最大流，肯定会超时，因此想到可能需要优化一下判断字符串满足条件的方法。

霍尔定理：
设二分图的两部分为，且。则定理描述为：二分图存在完美匹配，等价于对于的任意子集，与它们中任意点相连的的结点个数。

那么不妨统计下每个，中每种字符集的满足位置的数量，只要对于当前，中中字符集都满足条件，那么肯定存在一个完美匹配，即存在一种字符串分配方案满足条件。考虑到字典序最小，只需要从头开始填字符，每次都从到枚举判断是否满足条件。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n,m,cnt[10],f[maxn][1<<6],val[maxn];
char s[maxn],t[10],res[maxn];
bool check(int id)
{
    for(int i=0; i<(1<<6); i++)
    {
        int sum=0;
        for(int j=0; j<6; j++)
            if((i>>j&1))
                sum+=cnt[j];
        if(sum<f[id][i])
            return 0;
    }
    return 1;
}
int main()
{
    scanf("%s",s+1);
    m = strlen(s+1);
    for(int i=1; i<=m; i++)
        cnt[s[i]-'a']++;
    scanf("%d",&n);
    for(int i=1,x; i<=n; i++)
    {
        scanf("%d %s",&x,t+1);
        for(int j=1; t[j]; j++)
            val[x]|=(1<<(t[j]-'a'));
    }
    for(int i=m; i>=1; i--)
    {
        if(!val[i])
            val[i]=(1<<6)-1;
        for(int j=0; j<(1<<6); j++)
        {
            f[i][j]=f[i+1][j];
            if((j&val[i])==val[i])
                f[i][j]++;
        }
    }
    for(int i=1; i<=m; i++)
    {
        int flag=0;
        for(int j=0; j<6; j++)
        {
            if(!cnt[j]||(val[i]>>j&1)==0)
                continue;
            cnt[j]--;
            if(check(i+1))
            {
                flag=1;
                res[i]='a'+j;
                break;
            }
            else
                cnt[j]++;
        }
        if(!flag)
        {
            puts("Impossible");
            return 0;
        }
    }
    printf("%s\n",res+1);
    return 0;
}