呵呵。大家都知道五服以内不得通婚,即两个人最近的共同祖先如果在五代以内(即本人、父母、祖父母、曾祖父母、高祖父母)则不可通婚。本题就请你帮助一对有情人判断一下,他们究竟是否可以成婚?
输入格式:
输入第一行给出一个正整数N(2 ≤ N ≤10
4
),随后N行,每行按以下格式给出一个人的信息:
本人ID 性别 父亲ID 母亲ID
其中ID是5位数字,每人不同;性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考,则相应的ID位置上标记为-1。
接下来给出一个正整数K,随后K行,每行给出一对有情人的ID,其间以空格分隔。
注意:题目保证两个人是同辈,每人只有一个性别,并且血缘关系网中没有乱伦或隔辈成婚的情况。
输出格式:
对每一对有情人,判断他们的关系是否可以通婚:如果两人是同性,输出Never Mind;如果是异性并且关系出了五服,输出Yes;如果异性关系未出五服,输出No。
输入样例:
24
00001 M 01111 -1
00002 F 02222 03333
00003 M 02222 03333
00004 F 04444 03333
00005 M 04444 05555
00006 F 04444 05555
00007 F 06666 07777
00008 M 06666 07777
00009 M 00001 00002
00010 M 00003 00006
00011 F 00005 00007
00012 F 00008 08888
00013 F 00009 00011
00014 M 00010 09999
00015 M 00010 09999
00016 M 10000 00012
00017 F -1 00012
00018 F 11000 00013
00019 F 11100 00018
00020 F 00015 11110
00021 M 11100 00020
00022 M 00016 -1
00023 M 10012 00017
00024 M 00022 10013
9
00021 00024
00019 00024
00011 00012
00022 00018
00001 00004
00013 00016
00017 00015
00019 00021
00010 00011
输出样例:
Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
No
解题思路: 没有建树,关键点就是在怎么存储(int father[], int mother[]
),查找 (五代 以内(num计数)是否有共同的祖先(递归))。考虑到递归是因为每代都在重复做同样的事情,就是a,b是否有共同的爸爸妈妈。综上,我们可以得到函数式int judge(int a, int b, int num)
。
整体捋顺以后就考虑如何递归。要递归就要有递归边界和递归式。递归式:
考虑的就是啥叫近亲,判断的是a,b是否有共同的爸爸妈妈,a妈a爸,b妈b爸呢4个排列组合判断一下,只要不到第5代这个边界num就计数。
1 | return judge(mother[a], mother[b],num) && judge(mother[a], father[b], num) && judge(father[a],mother[b],num) && judge(father[a], father[b],num); |
递归边界:
- 特殊情况:有无法考证的 两方只要有一个咱们就直接算可牵手
- 有共同爸妈,直接掰掰
- 有5代内共同祖先,咱也掰掰
1 | if(a == -1 && b == -1 ) return 1; //牵手 |
注意:
1.有再婚的情况出现,爸妈的id也可以被输入做判断使用。因此录入数据的时候要顺带把爸爸妈妈的性别也补上去。sex[father[id]] = 'M'; sex[mother[id]] = 'F';
2.还有要记得初始化数组,因为有些父母的信息是不全的,没在录入id内,无祖先可考证要自己补充为-1;
3.再然后就是注意一些小语句的写法,好多时候不是思路,是不以为意的细节问题WA掉。
AC代码:
1 |
|