首页 > ACM题库 > HDU-杭电 > hdu 3431 Papa待解决[解题报告]C++
2014
03-23

hdu 3431 Papa待解决[解题报告]C++

Papa

问题描述 :

While cleaning your parents’ attic, you discovered a box containing many documents describing the relationships among your ancestors. Given these documents, you are interested in answering a number of questions about the relationships implied by the document. Fortunately, all your ancestors have unique names so it is possible to make many inferences without any confusion.

It is assumed that all relationships (implied or given) satisfy the following:

*A person can be either male, female, or have an unknown (undetermined by the data set) sex;
*a person can have at most one spouse (of the opposite sex), and X is Y’s wife if and only if Y is X’s husband;
*a person can have at most one mother and at most one father that can be inferred from the given data;
*if a person has a mother and father, then the mother and father are married;
*the children of a person’s spouse are that person’s children as well;
*the spouse of a son (or daughter) is not considered to be a daughter (or son). In other words, "sons" and "daughters" refer to biological sons and daughters.

The information provided will be consistent, and you may assume there are no hidden relationships that are not explicitly stated or implied by the above rules of consistency.

输入:

The first part of the input consists of a number of lines describing the known relationships. Each relationship is listed on one line in the form:

NAME is NAME’s RELATIONSHIP.

where NAME is a lowercase alphabetic word (never ‘is’), and RELATIONSHIP is one of

*wife
*husband
*daughter
*son
*mother
*father

This first part is terminated by a blank line. You may assume that there is at least one known relationship given, and there are at most 100 distinct names mentioned in the known relationships.

This is followed by a list of questions (one per line) of the form:
is NAME NAME’s RELATIONSHIP?
where NAME is as before, but RELATIONSHIP is one of

*wife
*husband
*daughter
*son
*mother
*father
*niece: X is a niece of Y if there are W and Z such that X is a daughter of W, and W and Y are distinct children of Z.
*nephew: X is a nephew of Y if there are W and Z such that X is a son of W, and W and Y are distinct children of Z.
*grandfather: X is a grandfather of Y if there is Z such that X is a father of Z, and Z is the father or mother of Y.
*grandmother: X is a grandmother of Y if there is Z such that X is a mother of Z, and Z is the father or mother of Y.
*grandson: X is a grandson of Y if there is Z such that X is a son of Z, and Z is a child of Y.
*granddaughter: X is a granddaughter of Y if there is Z such that X is a daughter of Z, and Z is a child of Y.

All names appearing in the questions will be mentioned in the list of known relationships. The list of questions is terminated by the end of file.

输出:

The first part of the input consists of a number of lines describing the known relationships. Each relationship is listed on one line in the form:

NAME is NAME’s RELATIONSHIP.

where NAME is a lowercase alphabetic word (never ‘is’), and RELATIONSHIP is one of

*wife
*husband
*daughter
*son
*mother
*father

This first part is terminated by a blank line. You may assume that there is at least one known relationship given, and there are at most 100 distinct names mentioned in the known relationships.

This is followed by a list of questions (one per line) of the form:
is NAME NAME’s RELATIONSHIP?
where NAME is as before, but RELATIONSHIP is one of

*wife
*husband
*daughter
*son
*mother
*father
*niece: X is a niece of Y if there are W and Z such that X is a daughter of W, and W and Y are distinct children of Z.
*nephew: X is a nephew of Y if there are W and Z such that X is a son of W, and W and Y are distinct children of Z.
*grandfather: X is a grandfather of Y if there is Z such that X is a father of Z, and Z is the father or mother of Y.
*grandmother: X is a grandmother of Y if there is Z such that X is a mother of Z, and Z is the father or mother of Y.
*grandson: X is a grandson of Y if there is Z such that X is a son of Z, and Z is a child of Y.
*granddaughter: X is a granddaughter of Y if there is Z such that X is a daughter of Z, and Z is a child of Y.

All names appearing in the questions will be mentioned in the list of known relationships. The list of questions is terminated by the end of file.

样例输入:

john is mary's husband.
john is tom's father.
mary is jane's mother.
jane is anna's mother.

is mary john's wife?
is jane mary's daughter?
is tom mary's husband?
is anna jane's daughter?

样例输出:

yes
yes
no
unknown


  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  2. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?