首页 > ACM题库 > HDU-杭电 > hdu 3258 Intricate to death?待解决[解题报告]C++
2014
03-13

hdu 3258 Intricate to death?待解决[解题报告]C++

Intricate to death?

问题描述 :

Have you heard of the game PAL? Many people believe it’s the greatest Chinese RPG series so far. There are many characters, including heros and NPCs, summarized in the following paragraph.
李 逍 遥:一代主角。
赵 灵 儿:一代主角的妻子。
李 三 思:一代主角的爸爸。
李 忆 如:一代主角的女儿。
酒 剑 仙:一代主角的师父。
王 小 虎:一代主角的邻居。
林 月 如:一代主角的第一个知己。
阿  奴:一个主角的第二个知己。
林 青 儿:一代主角的妻子的妈妈。
巫  王:一代主角的妻子的爸爸。
景  天:一代主角的爸爸的师父。
独孤剑圣:一代主角的师父的师兄。
喻 南 松:一代主角的邻居的朋友。
圣  姑:一代主角的妻子的守护人。
沈 欺 霜:一代主角的邻居的女朋友。
千叶禅师:一代主角的邻居的朋友的师父。
紫  萱:一代主角的妻子的妈妈的妈妈。
铁掌飞凤:一代主角的爸爸的弟弟的妻子。
龙  葵:一代主角的爸爸的师父的前世的妹妹。
飞  蓬:一代主角的爸爸的师父的前世的前世。
徐 长 卿:一代主角的妻子的妈妈的妈妈的丈夫的转世。
夕  瑶:一代主角的爸爸的师父的前世的前世的女朋友。
清  微:一代主角的妻子的妈妈的妈妈的丈夫的转世的师父。
周 赤 炎:一代主角的妻子的妈妈的妈妈所救的狼妖的人的身份。
燎  日:一代主角的妻子的妈妈的妈妈所救的狼妖的妖的身份。
慕容紫英:一代主角的爸爸的师父的前世铸的剑的第一个发现者。
苏  媚:一代主角和一代主角的第一个知己所杀的妖怪的孩子。
云 天 河:一代主角的爸爸的师父的前世铸的剑的第一个发现者的师侄。
拜月教主:一代主角和一代主角的妻子和一代主角的妻子的妈妈的仇人。
云 天 青:一代主角的爸爸的师父的前世铸的剑的第一个发现者的师侄的爸爸。
怀  朔:一代主角的爸爸的师父的前世铸的剑的第一个发现者的师侄的师兄。
璇  玑:一代主角的爸爸的师父的前世铸的剑的第一个发现者的师侄的师姐。
韩 菱 纱:一代主角的爸爸的师父的前世铸的剑的第一个发现者的师侄的女朋友。
玄  霄:一代主角的爸爸的师父的前世铸的剑的第一个发现者的师侄的爸爸的师兄。
夙  玉:一代主角的爸爸的师父的前世铸的剑的第一个发现者的师侄的爸爸的妻子。
南 宫 煌:一代主角的妻子的妈妈的妈妈所救的狼妖的人的身份的两个儿子中的弟弟。
星  璇:一代主角的妻子的妈妈的妈妈所救的狼妖的人的身份的两个儿子中的哥哥。
重  楼:一代主角的爸爸的师父和一代主角的爸爸的师父的前世的前世的朋友兼敌人。
柳 梦 璃:一代主角的爸爸的师父的前世铸的剑的第一个发现者的师侄的爸爸所救的女妖。
思  堂:一代主角的妻子的妈妈的妈妈所救的狼妖的人的身份的两个儿子中的哥哥的朋友。
王 蓬 絮:一代主角的妻子的妈妈的妈妈所救的狼妖的人的身份的两个儿子中的哥哥的女朋友。
温  慧:一代主角的妻子的妈妈的妈妈所救的狼妖的人的身份的两个儿子中的弟弟的女朋友。
雪  见:一代主角的爸爸的师父的前世的前世的女朋友给一代主角的爸爸的师父做的女朋友。
婵  幽:一代主角的爸爸的师父的前世铸的剑的第一个发现者的师侄的爸爸所救的女妖的妈妈。
花  楹:一代主角的爸爸的师父的前世的前世的女朋友给一代主角的爸爸的师父做的女朋友的宠物。
温  策:一代主角的妻子的妈妈的妈妈所救的狼妖的人的身份的两个儿子中的弟弟的女朋友的哥哥。
归  邪:一代主角的爸爸的师父的前世铸的剑的第一个发现者的师侄的爸爸所救的女妖的妈妈的手下武将。
奚  仲:一代主角的爸爸的师父的前世铸的剑的第一个发现者的师侄的爸爸所救的女妖的妈妈的手下文官。

Obviously, some of the descriptions are deliberately lengthened, in order to make the whole paragraph more fun.
In this problem, your task is similar: given a set of rules, find a description that is at least A characters and at most B characters long.
If there are more than one possible description satisfying the condition above, choose the one that comes first lexicographically.
Note that shorter answers are NOT always better than longer ones.
BTW: Rules like "Lixiaoyao: Lixiaoyao" looks rather stupid, so don’t print things like that, even if no other solutions can be found.

输入:

The first line contains a single integer T (T <= 10), the number of test cases.
Each case begins with an integer n (1 <= n <= 5), the number of rules, followed by n lines, each describing a rule. Each rule begins with the character’s name, then a colon, then a single space, and the description. The description is a list of tokens separated by a single space, with no leading spaces or trailing spaces, followed by a period. Each token is either a word consisting of only lowercase letters, or a character’s name, or a character’s name, followed by an apostrophe(‘), then a lowercase letter ‘s’. A character’s name is always an uppercase letter followed by zero or more lowercase letters. No two characters will have the same name, but not all character names appear in the left side of a rule. After the ruleset, you’ll be given a single integer q (1 <= q <= 5) on the next line, indicating the number of queries. Each query appears on its own line, containing the name of the character in question, then two integers A and B (1 <= A <= B <= 100), explained above.
Each rule is at least 15 characters, at most 100 characters, containing at least one lowercase token. On the right side of each rule, there will be at most 3 characters involved, all distinct (though one of them may appear on the left side of the rule), and there are no more than 10000 different descriptions for any character in questions, if we only count descriptions only length <= B.

输出:

The first line contains a single integer T (T <= 10), the number of test cases.
Each case begins with an integer n (1 <= n <= 5), the number of rules, followed by n lines, each describing a rule. Each rule begins with the character’s name, then a colon, then a single space, and the description. The description is a list of tokens separated by a single space, with no leading spaces or trailing spaces, followed by a period. Each token is either a word consisting of only lowercase letters, or a character’s name, or a character’s name, followed by an apostrophe(‘), then a lowercase letter ‘s’. A character’s name is always an uppercase letter followed by zero or more lowercase letters. No two characters will have the same name, but not all character names appear in the left side of a rule. After the ruleset, you’ll be given a single integer q (1 <= q <= 5) on the next line, indicating the number of queries. Each query appears on its own line, containing the name of the character in question, then two integers A and B (1 <= A <= B <= 100), explained above.
Each rule is at least 15 characters, at most 100 characters, containing at least one lowercase token. On the right side of each rule, there will be at most 3 characters involved, all distinct (though one of them may appear on the left side of the rule), and there are no more than 10000 different descriptions for any character in questions, if we only count descriptions only length <= B.

样例输入:

2
2
Alice: Bob's mother.
Bob: Alice's son.
2
Alice 20 20
Bob 24 25
4
A: B's girlfriend.
B: A's boyfriend.
C: the only person who knows that A and B love each other.
A: D's smallest daughter.
5
A 1 100
C 1 50
C 70 80
C 71 80
C 82 90

样例输出:

Case 1:
Alice: Bob's mother.
Bob: Bob's mother's son.
Case 2:
A: A's boyfriend's girlfriend.
No solution.
C: the only person who knows that A and A's boyfriend love each other.
C: the only person who knows that B's girlfriend and B love each other.
C: the only person who knows that A and B's girlfriend's boyfriend love each other.


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  4. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。