看上去像是匹配，字典序最小？无法保证。

贪心处理？

不妨考虑从前到后，尽量填小的，要使得后面一定有解即可！

相当于一个完美匹配！

根据Hall定理，枚举字符集子集s，使得s的所有个数小于等于相邻的点个数

又是后缀，所以预处理，b[i][s]，[i,n]，可填集合和s有交集的位置的数量。

验证即可。

O(6*2^6*n)

 

注意无解Impossible

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}template
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Modulo{const int mod=998244353;int ad(int x,int y){ return (x+y)>=mod?x+y-mod:x+y;}void inc(int &x,int y){x=ad(x,y);}int mul(int x,int y){ return (ll)x*y%mod;}void inc2(int &x,int y){x=mul(x,y);}int qm(int x,int y=mod-2){ int ret=1;while(y){ if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}}//using namespace Modulo;namespace Miracle{const int N=1e5+5;int buc[6];int a[N],b[N][1<<6];int sz[1<<6];char s[N],cc[233];int n;int lim=(1<<6)-1;bool che(int p,int c){ for(reg s=1;s<=lim;++s){ int lp=sz[s]; if(s&(1<
           
            b[p][s]) return false; } return true;}int main(){ scanf("%s",s+1); n=strlen(s+1); for(reg i=1;i<=n;++i){ ++buc[s[i]-'a']; a[i]=lim; } int m;rd(m); for(reg i=1;i<=m;++i){ int p;rd(p); a[p]=0; scanf("%s",cc+1); int l=strlen(cc+1); for(reg j=1;j<=l;++j){ a[p]|=(1<<(cc[j]-'a')); } } for(reg i=n;i>=1;--i){ for(reg t=0;t<=lim;++t){ b[i][t]=b[i+1][t]; if(t&a[i]) ++b[i][t]; } } for(reg s=0;s<=lim;++s){ sz[s]=0; for(reg j=0;j<6;++j){ if(s&(1<