# Papa

问题描述 :

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.

输入:

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.

输出:

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

swap写成内联函数会不会好一些

I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

妈呀！这个Dijkstra模板好长OwQ！

简洁的代码

对，就是把这32位当成一个长度为32的数

额楼主能否在发布代码的同时对解题思路做个讲解呢？这样大家在学习的时候就方便多了。

可以用公式。主要为了说明动态规划，如果要打表的话，这种方法也是较简单和高效的

哇，算法有这么多呢！

总结的很全面，学习了！

第23行：

hash = -1是否应该改成hash[s ] = -1

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

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

代码是给出了，但是解析的也太不清晰了吧！如 13 abejkcfghid jkebfghicda

第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)，为什么要这样拆分，原则是什么？

看似简单，还是不少坑的

为什么暴力求解方法循环到sqrt(n) 就可以了呢