题解：CF1009G Allowed Letters
Union_of_Britain
2024-04-16 13:28:43
一个 $O(|\Sigma|^2n)$ 的做法。
字典序最小，则从前往后选能选的最小的。
现在压力给到如何判定。容易想到网络流判定，但是看上去每次判定一下复杂度有点爆炸。那么先尝试从后往前构造一组合法解。根据 [CF1168E](https://www.luogu.com.cn/problem/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$ 的。
最后构造答案时类似地动态判定即可。需要注意的是后面不能挪用前面的（时代的抉择）。
这样我们就使用更优的复杂度解决了这道题。
很史的考场代码：
```cpp
#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;
}
```