L2-016. 愿天下有情人都是失散多年的兄妹

時間限制

200 ms

內存限制

65536 kB

代碼長度限制

8000 B

判題程序

Standard

作者

陳越

完全轉載:https://blog.csdn.net/priestessofbirth/article/details/78277297

呵呵。大家都知道五服以內不得通婚，即兩個人最近的共同祖先如果在五代以內（即本人、父母、祖父母、曾祖父母、高祖父母）則不可通婚。本題就請你幫助一對有情人判斷一下，他們究竟是否可以成婚？

輸入格式：

輸入第一行給出一個正整數N（2 <= N <= 104），隨后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

---

提交代碼

?

解題思路：

這題目有趣，哈哈哈，有意思。題目意思不難，但分析起來有一定難度。還是按照以前的習慣，樹的題目不建樹，用前驅數組儲存和查找。一開始的時候定義一個足夠大的字符串數組，值存放對應編號人的性別，別的不存儲，后面需要用到性別的判定。，用一個父親數組存放該節點的父親，用一個母親數組存放該節點的母親，但不管是父親還是母親一定要記得設置性別，要不然會有一些點過不去，你知道父母親性別，系統可不知道。全部存儲完之后就是輸入數據要你判斷了，首先判斷是否為同性，同性就不用管了，人家可是真愛，沒有任何問題，不能拆散。異性那就需要判斷了。我們先判斷雙方父母是否可以考證，如果其中有一個不可考證那就恭喜你們了，為了真愛就算這一步判斷過了，沒有任何問題，如果都可以考證，再判斷男女雙方的父親和母親是否為一個人，是一個人那就肯定不行了，這可不是皇族。如果不是那就趕緊計算一下這是第幾代了，滿了五代就趕緊退出，匯報沒有問題，再往上查會發生什么誰也不知道，牽手成功就趕緊走吧，恭喜啦。沒到五代就別高興的太早了，判斷男方父親和女方父親的父母情況，男方母親和女方母親的情況，男方母親和女方母親的情況，男方父親和女方母親的情況。當然不用額外考慮。男方父親和女方母親是否在一起和男方母親和女方父親是否在一起的情況，現實并不是天龍八部，不可能每個男生都是段譽。O(∩_∩)O哈哈哈~判斷過程就是這樣，具體的自己再跟著解題思路慢慢推一遍

#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define N 100000+10 char sex[N]; int father[N],mother[N]; int judge(int a,int b,int num){ if(a == -1&&b == -1){//善意的愛護，如果無法考證就算是符合 return 1; } if(mother[a] != -1&&mother[a] == mother[b]||father[a] != -1&&father[a] == father[b]){ return 0;//父母親可以考證，且相同，那可是不行的，@@@@@@@ } num++; if(num >= 4){ return 1;//超過了五代就牽手成功了，哈哈哈，有情人終成眷屬了 } return judge(mother[a],mother[b],num)&&//別激動，判斷一下你們的父母是不是近親 judge(father[a],father[b],num)&& judge(mother[a],father[b],num)&&//判斷你的老媽和他的老爸是不是近親 judge(father[a],mother[b],num); //判斷你的老爸和他的老媽是不是近親 } int main(){ // freopen("input.txt","r",stdin); int n,m; memset(father,-1,sizeof(father)); memset(mother,-1,sizeof(mother)); scanf("%d",&n); for(int i = 0;i < n;i++){ int id; char ch; scanf("%d",&id); getchar();//吸收空格，沒有這句很神奇，基本上全都可以，好人啊 scanf("%c",&sex[id]); scanf("%d",&father[id]); sex[father[id]] = 'M';//注意一下爸媽也是要設置性別哦 scanf("%d",&mother[id]); sex[mother[id]] = 'F';//性別別設錯了，男女有別哦 } scanf("%d",&m); for(int i = 0;i < m;i++){ int a,b; scanf("%d%d",&a,&b); if(sex[a] == sex[b]){//同性的就不用管了，這可是真愛 printf("Never Mind\n"); }else{ if(judge(a,b,0)){ printf("Yes\n"); }else{ printf("No\n"); } } } return 0; }

?

總結

以上是生活随笔為你收集整理的PAT L2-016. 愿天下有情人都是失散多年的兄妹的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。