CF1009G Allowed Letters 题解

题目链接

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

$$n,m\leq10^5$$

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

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

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

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

复习霍尔定理:

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

$$X = \{x_1 , x_2 ,…,x_m\}, Y  = \{y_1 ,y_2 , … , y_n \}$$

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

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

最终上代码。

 

\(\)

发表评论

电子邮件地址不会被公开。 必填项已用*标注