国外ps素材网站大数据营销系统怎么样

题意：给定一个长为n的串，字符集’a’~‘f’。你可以重排这个串，满足指定m个位置上只能放特定的字符，m个位置以及字符集会给出,求字典序最小的串

这题是不错的考验hall定理的题。

思路大概是从前向后做，如果填了这个数后面的依然可行就可以填
根据hall定理，我们需要枚举之后的每个子集并判断相邻的节点是否大于size
我们从后向前处理$f[i][j]$表示从$i-n$有多少点连的边被包括，$j<=2<<6$
再处理出$cnt[j]$表示有多少个字母可以填入$j$
每次只要看看是否每个点集都满足，即取出这个点后$f[i][j]<cnt[j]$

#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e5+7;
const int Mx=1<<6;
int n,m;
char s[N],ans[N];
int cnt[Mx],f[N][Mx],e[N];
int main() {scanf("%s",s+1);n=strlen(s+1);for (int i=1;i<=n;i++) {for (int j=0;j<Mx;j++) {if (j&(1<<(s[i]-'a'))) cnt[j]++;//表示组合为j的有多少种方式满足 }}for (int i=1;i<=n;i++) e[i]=Mx-1;scanf("%d",&m);for (int i=1,pos,ln;i<=m;i++) {scanf("%d%s",&pos,s+1);e[pos]=0;ln=strlen(s+1);for (int j=1;j<=ln;j++) e[pos]|=1<<(s[j]-'a');}for (int i=n;i;i--) {for (int j=0;j<Mx;j++) {f[i][j]+=f[i+1][j];if ((j&e[i])==e[i]) f[i][j]++; }}for (int i=1,flg,ok;i<=n;i++) {flg=0;for (int j=0;j<6;j++) {if ((e[i]>>j&1)==0 || !cnt[1<<j]) continue;ok=1;for (int k=0;k<Mx;k++) {if (f[i+1][k]>cnt[k]-(k>>j&1)) {//保证对于每个k都满足 ok=0;break;}}if (ok) {flg=1;ans[i]=j+'a';for (int k=0;k<Mx;k++) if (k>>j&1) cnt[k]--;break;}}if (!flg) return puts("Impossible"),0;}puts(ans+1);
}