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; }