CF1009G Allowed Letters 题解

题目链接

这一道题题面大概是有一个包含a,b,c,d,e,f六种字符的字符串（长度为n），要求它的一个重新排列的字符串，其中有m位可能有对填写的字母的限制。其中保证

要求输出字典序最小的可能解，如果无解输出”Impossible”。

很容易想到的基本思路就是，对于每一位字母，从a到f枚举是否能够填在这一位，如果能够填，就填字母。如果枚举到f，然而仍然没能找到可能的解，则输出无解。这样字典序就会最小。

于是问题的关键便转化为如何判断对于某一位填写某个字母之后，剩下的位能不能全部成功找到匹配，而这个问题又能够转化为图的匹配。

转化为图的匹配之后，问题就能够使用霍尔定理来解决了。

复习霍尔定理：

二部图G中的两部分顶点组成的集合分别为

,G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是：X中的任意k个点至少与Y中的k个点相邻。(1≤k≤m)。

而在本题中，则是代表在如后面的尚未填充的字母位中的任意k个都能够找到至少k个能够填写的原字符串中尚未使用的字符，就代表后面尚未填写的字符一定有一种方法能够填写。

最终上代码。

// Author : WangZhikun
// Date   : 2018.07.27

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int n,m,msk[100020],p,fn[80] = {0},gn[80] = {0},ccnt[10] = {0};
char s[100020],cm[10],ans[100020];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	for(int i=0;i<100010;i++)msk[i] = 63;
	cin>>s;
	n = (int)strlen(s);
	cin>>m;
	
	for(int i=0;i<m;i++){
		cin>>p>>cm;
		p-=1;
		msk[p] = 0;
		for(int i=0;i<strlen(cm);i++) 
			if(cm[i]>='a' && cm[i]<='f')
				msk[p]+=1<<(cm[i]-'a');
	}
	for(int i=0;i<n;i++){
		fn[msk[i]]++;
		ccnt[s[i]-'a']+=1;
	}
	for(int i=0;i<64;i++){
		for(int j=0;j<64;j++)if((i&j) == j)gn[i]+=fn[j];
	}
	for(int po=0;po<n;po++){
		ans[po] = 'u';
		for(int i=0;i<64;i++)if((i&msk[po]) == msk[po])gn[i]-=1;
		for(int c = 0;c<6;c++){
			if((msk[po] & (1<<c)) == 0)continue;
			ccnt[c]-=1;
			int co = 1,ccn = 0;
			for(int i=0;i<64;i++){
				ccn = 0;
				for(int j=0;j<6;j++)if(i&(1<<j))ccn+=ccnt[j];
				if(ccn<gn[i]){
					co = 0;
					break;
				}
			}
			if(co){
				ans[po] = 'a'+c;
				break;
			}
			else{
				ccnt[c]+=1;
			}
		}
		if(ans[po] == 'u'){
			cout<<"Impossible"<<endl;
			return 0;
		}
	}
	cout<<ans<<endl;
	return 0;
}

[latex]