BZOJ 3012 [Usaco2012 Dec]First!

发布于 2017-07-07  81 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3012

题意:给定 n 个总长不超过 m 的互不相同的字符串,现在你可以任意指定字符之间的大小关系。问有多少个串可能成为字典序最小的串,并输出这些串。


考虑什么串不能作为字典序最小的串:如果有串是它的前缀,显然不行,那么其他情况我们可以尝试去指定大小关系,对于这个串上所有点向它的兄弟们连边,表示这个点小于那些点。

最后判断新图是否存在环,若存在,则必不能满足我们钦定的所有关系

读入是坑点... 实际上没有单词比 30 长... 所以可以开数组

又 WA 又 RE... 果然意识模糊后不适合调 WA 的题...

 


一个非常弱的准退役OIER