题解：CF1009G Allowed Letters

一个 O(|\Sigma|^2n) 的做法。

字典序最小，则从前往后选能选的最小的。

现在压力给到如何判定。容易想到网络流判定，但是看上去每次判定一下复杂度有点爆炸。那么先尝试从后往前构造一组合法解。根据 CF1168E 的想法，考虑根据后面的解来调整。

具体来说，当前 p_1 我想选 s，s 却没有了，那么就找到后面的一个填 a 的位置 p_2，让它滚（必要的牺牲）。

那么这个 p_2 怎么办？我让另一个位置 p_3 腾位置出来就可以了。如果有解，最后一定会在某个位置 p_m 结束（历史的必然）。

注意到我只关心两个事情：这个路径上的位置可以做这样的替换，并且最后 p_m 变成的字符 t 必须是有余的。那么我把它看成在字符集大小的图上的路径 P:s\to t。同时也说明了这样的路径长度大小 \le |\Sigma|。

这样的图怎么构造呢？对于每个已经确定为 c_i 的位置 i，从 c_i 连向 u，并且标记为 i 的转移，如果 u\neq c_i 并且 u 被允许放在 i 位置。两个节点的连边集合，由于涉及插入、删除和找任意一个，可以选用 unordered_set。找到这样的路径之后，修改图即可。修改量是单次 |\Sigma|^2 的。

最后构造答案时类似地动态判定即可。需要注意的是后面不能挪用前面的（时代的抉择）。

这样我们就使用更优的复杂度解决了这道题。

很史的考场代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int cur[maxn],sze[6],n,m,alo[maxn][7],vis[6],can[6];
char s[maxn];
unordered_set<int> d[6][6];
#define VI vector<int>
VI CUR;
bool dfs(int u,int t){
    if(u==t)return 1;
    vis[u]=1;
    for(int i=0;i<6;i++){
        if(vis[i])continue;
        if(d[u][i].size()){
            CUR.push_back(i);
            if(dfs(i,t))return 1;
            CUR.pop_back();
        }
    }
    return 0;
}
void DFS(int u){
    can[u]=1;
    for(int i=0;i<6;i++){
        if(can[i])continue;
        if(d[i][u].size())DFS(i);
    }
}
VI findpath(int u,int v){
    CUR={u};
    for(int i=0;i<6;i++)vis[i]=0;
    if(dfs(u,v))return CUR;
    return {};
} 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>s+1;n=strlen(s+1);
    cin>>m;
    for(int i=1;i<=m;i++){
        int k;string s2;
        cin>>k>>s2;
        for(auto u:s2)alo[k][u-'a']=1;
        alo[k][6]=1;
    }
    for(int i=1;i<=n;i++){
        if(!alo[i][6])for(int j=0;j<6;j++)alo[i][j]=1;
    }
    for(int i=1;i<=n;i++)sze[s[i]-'a']++;
    for(int i=n;i>=1;i--){
        bool flg=0;
        for(int j=0;j<6;j++){
            if(!sze[j])continue;
            if(alo[i][j]){
                sze[j]--;cur[i]=j;
                for(int k=0;k<6;k++)if(alo[i][k]&&j!=k)d[j][k].insert(i);
                flg=1;break;
            }
            VI F;
            for(int k=0;k<6;k++)can[k]=0;
            DFS(j);
            for(int k=0;k<6;k++){
                if(j!=k&&can[k]&&alo[i][k]){
                    F=findpath(k,j);
                    int t[7];
                    for(int i=0;i<F.size()-1;i++)t[i]=(*d[F[i]][F[i+1]].begin()),sze[F[i]]++,sze[F[i+1]]--;
                    for(int i=0;i<F.size()-1;i++){
                        cur[t[i]]=F[i+1];
                        for(int l=0;l<6;l++)if(alo[t[i]][l]&&l!=F[i+1])d[F[i+1]][l].insert(t[i]);
                        for(int l=0;l<6;l++)if(alo[t[i]][l]&&l!=F[i])d[F[i]][l].erase(t[i]);
                    }
                    sze[k]--;
                    cur[i]=k;
                    for(int l=0;l<6;l++)if(alo[i][l]&&l!=k)d[k][l].insert(i);
                    flg=1;
                    break;
                }
            }
            if(flg)break;
        }
        if(!flg)return cout<<"Impossible"<<endl,0;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<6;j++)if(alo[i][j]&&j!=cur[i])d[cur[i]][j].erase(i);
        int res=-1;
        for(int k=0;k<6;k++)can[k]=0;
        DFS(cur[i]);
        for(int j=0;j<cur[i];j++){
            if(!alo[i][j]||!can[j])continue;
            VI F=findpath(j,cur[i]);
            int t[7];
            for(int i=0;i<F.size()-1;i++)t[i]=(*d[F[i]][F[i+1]].begin());
            for(int i=0;i<F.size()-1;i++){
                cur[t[i]]=F[i+1];
                for(int l=0;l<6;l++)if(alo[t[i]][l]&&l!=F[i+1])d[F[i+1]][l].insert(t[i]);
                for(int l=0;l<6;l++)if(alo[t[i]][l]&&l!=F[i])d[F[i]][l].erase(t[i]);
            }
            res=j;
            break;
        }
        if(res==-1)res=cur[i];
        cur[i]=res;
        cout<<(char)(res+'a');
    }
    return 0;
}