codeforces 623 A. Graph and String (构造)

题目链接:题目链接

题意:给出一个无向图,该图是通过仅包含‘a’ ‘b’ ‘c’三个字母,以规则“i,j之间有边,当且仅当s[i]和s[j]相同,或者s[i]和s[j]在字母表中相邻”(也就是只有’a’和’c’是没有边相连的)得到的,现在问能否还原这个字符串,如果能,输出任意一个解。

思路:其实就是简单构造。。。

构造的一个技巧是。。把能确定的地方先确定了。。。。

我们发现’b’比较特殊。。因为b和任意点都相连。。。

于是可以统计一下度。。。然后确定字符串中的b

然后对于某个没有确定的位置,我放置一个a,并且把所有和这个位置相连的都放成a

字符串中剩下的没有确定的位置就一定是c了。

这个时候我再判断是否满足题中图的条件。

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz