codeforces1009G Allowed Letters【贪心+hall定理】

因为是字典序所以贪心选当前能选的最小的，所以问题就在于怎么快速计算当前这个位置能不能选枚举的字母

重排之后的序列是可以和原序列完美匹配的，而完美匹配需要满足hall定理，也就是左边任意k个集合一定和右边至少k个点相连

又一共6个字符，原序列中相同字符点连出的点集是一样的，所以只要2^6个字符集合满足hall定理，每次这样枚举状压判断一下即可

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=100005;

int n,m,sm[N],f[N][70],ok[N];

char s[N],c[10],flg,ans[N];

int main()

{

	scanf("%s%d",s+1,&m);

	n=strlen(s+1);

	for(int i=1;i<=n;i++)

		for(int j=0;j<(1<<6);j++)

			if(j&(1<<(s[i]-'a')))

				sm[j]++;

	for(int i=1;i<=n;i++)

		ok[i]=(1<<6)-1;

	for(int i=1,x;i<=m;i++)

	{

		scanf("%d%s",&x,c+1);

		ok[x]=0;

		for(int j=1;j<=strlen(c+1);j++)

			ok[x]+=(1<<(c[j]-'a'));

	}

	for(int i=n;i>=1;i--)

		for(int j=0;j<(1<<6);j++)

			f[i][j]=f[i+1][j]+(((j&ok[i])==ok[i])?1:0);

	for(int i=1;i<=n;i++)

	{

		bool fl=0;

		for(int j=0;j<6&&!fl;j++)

			if(sm[1<<j]&&(ok[i]&(1<<j)))

			{

				flg=1;

				for(int k=0;k<(1<<6)&&flg;k++)

					if(f[i+1][k]>sm[k]-((k>>j)&1))

						flg=0;

				if(flg)

				{

					fl=1;

					ans[i]='a'+j;

					for(int k=0;k<(1<<6);k++)

						if(k&(1<<j))

							sm[k]--;

				}

			}

		if(!flg)

		{

			puts("Impossible");

			return 0;

		}

	}

	for(int i=1;i<=n;i++)

		printf("%c",ans[i]);

	return 0;

}

巴特西

codeforces1009G Allowed Letters【贪心+hall定理】

最新文章

热门文章