Catnyms解题报告byJohn.docVIP

Catenyms解题报告 学号：不详 姓名：钟鏸 日期：2011.6.10-2011.6.20 题目 0/ZQUOJ/problem/Problem.jsp?id=1394 题意 catenym是用一个连接符号( .)串接起来的两个单词，其中，前一个单词的最后一个字母，与后一个单词的第一个字母，是一样的。如题干所示，下面就是两个catenym： dog . gopher 或 gopher . rat 然后，题干定义一个“组合catenym”就是若干个前后相连起来的catenym，如：aloha.aloha.arachnid.dog.gopher.rat.tiger （前一个单词的最后一个字母 = 下一个单词的第一个字母） 现题目给出若干个单词，让我们构造一个“组合catenym”。构造时，要求每个单词都出现一次，且仅一次。 题意弄懂之后，还有几个事项是需要注意的： 1. 给出的单词，不一定是按照字典序从小到大的顺序给出的，因此有可能需要排序 2. 问题的规模是1000个单词 3. 所给的若干个单词，存在构造不出一个“组合catenym”的可能性，即无解，此时输出*** 4. 关于“the lexicographically least compound catenym”，为什么提出要“字典序最小”？ 如何去满足这个“字典序最小”的条件？ 分析 题目要求把所有单词前后连接在一起，每个单词出现一次且仅一次，看起来就是一个排列问题，用穷举法貌似可以解决。但问题规模达到1000个单词，那么，就有1000！种排列，要从这1000！种排列中判断是否存在满足“组合catenym”条件的排列，如存在，则寻找字典序最小的排列。总的计算量非常巨大。“超时”是必然结果。 题目所给的第一个样例太简单了，一眼就能看出可以构造出“组合catenym”，所以不具有什么代表性。因此，需要我们自己设计一些具有代表性的例子： 例1： ejjjc assse bfffa dkkkb ebbd bnnna dcccb ayyye 由于catenym涉及的只是单词的首字母以及最后一个字母，对于单词中间的字母以及长度，是根本不敏感的，所以，在设计这些单词的时候，中间的字母都是随意设计。 经过尝试，对于例1，我们可以构造出多个“组合catenym”： dkkkb.bfffa.assse.ebbd.dcccb.bnnna.ayyye.ejjjc —— ① dcccb.bnnna.ayyye.ebbd.dkkkb.bfffa.assse.ejjjc —— ② dcccb.bfffa.assse.ebbd.dkkkb.bnnna.ayyye.ejjjc —— ③ …… 因此，如果不给出限制条件，答案是不唯一的。正因为如此，题目才给出“字典序最小”这个条件，使得答案唯一。对于例1，正解是③。 例1告诉我们答案的多样性，以及如何根据题目条件选择合适的答案。那么，什么情况下会出现无解呢？ 题目所给的第二个样例同样是太简单，一眼就看出不能构造出“组合catenym”：因为单词oak无法与任何其他单词前后连接起来。 有没有具有代表性的无解的例子呢？ 我们可以思考设计出这样的例子： 例2：akkkb annnc bfffc 例3：akkkb acccb bfffc bjjjc 例2和例3都是无法满足“使用全部单词一次且仅一次”这个条件来构造出“组合catenym”的。 通过以上分析，自然而然打算采用“有哪些信誉好的足球投注网站”策略来解题，希望通过有哪些信誉好的足球投注网站解空间，寻找符合题目条件的正解。（如果我们没有这样的想法，说明我们没接触过“有哪些信誉好的足球投注网站”法，或者还没有建立“有哪些信誉好的足球投注网站”策略的思维。） 如果没有接触过“欧拉图”或“半欧拉图”的概念，自然打算用朴素的“深度优先有哪些信誉好的足球投注网站DFS”来求解本题。（广度优先有哪些信誉好的足球投注网站BFS在理论上可以求解本题，但BFS多用在求最短路径，用于本题速度很慢） 如果没有时间上的限制，或者问题规模较小，朴素的DFS是可以求得正解的。对例1画出有哪些信誉好的足球投注网站过程的示意图如下： 说明：DFS有哪些信誉好的足球投注网站过程中，为了尽快搜到正解，每一步在有多个单词可供选择时，先选择字典序小的单词，这样这样可以尽快搜到正解（满足字典序最小的“组合catenym”），避免遍历整棵有哪些信誉好的足球投注网站树。 以上做法虽然看似可以求解问题，但是，考虑到问题的数据规模：1000个单词，那么，有哪些信誉好的足球投注网站树高度最多可达1000层，第一层有1000个节点，第二层有1000*999个节点，第三层有1000*999*998各节点，依此类推，那么，这棵有哪些信誉好的足球投注网站树是极为庞大的。 此外，由例1的有哪些信誉好的足球投注网站图解，必须想到的是，按字典序选择最小的单词作为第一个单词，往往求不出一个可能解。 根据经验，这些题目的大多数测试数据的正解往往不在有哪些信誉好的足球投注网站树的左下角，平均几率是在有哪些信誉好的足球投注网站树的中间底部位置