天梯题集——冰岛人（隐藏条件：考虑嫡系）

电玩女神 2022-12-24 09:56 124阅读 0赞

#### 前文 ####

[愿天下有情人都是失散多年的兄妹][Link 1] 与 冰岛人 解题思路几乎是同理的，不过这里需要考虑多一个**是否嫡系的关系**。  
（卡了我好久、又来一个隐藏条件，长知识、长知识…）。  
用递归实现很容易出现超时，循环果然比递归效率高。  
[循环与递归效率的比较][Link 2]

#### 冰岛人 ####

![t1][]  
![t2][]  
![t3][]

--------------------

#### 解题难点 ####

**①、记录数据——映射+结构体**

struct node{ 
    	string fa;
    	int sex;
    };
    map <string, node> num;

第一次把映射和结构体结合起来，查询方便了许多。

--------------------

**②、判断 m1 与 m2 是否是嫡亲**

//判断 s1 是否为 s2 的嫡系
    bool judge1(string s1, string s2){ 
    	for(string A=s1; !A.empty(); A=num[A].fa)
    		if(A==s2) return false;
    	return true;
    }

--------------------

**③、m1 与 m2 五代以内无有公共祖先**

//s1与s2五代以内无有公共祖先 
    bool judge2(string s1, string s2){ 
    	int i=1;
    	string A, B;
    	for(A=s1; !A.empty()&&i<=5; i++){ 
    		int j=1;
    		for(B=s2; !B.empty()&&j<=5; j++){ 
    			if(A==B&&(i<5||j<5))
    				return 0;
    			B=num[B].fa;
    		}
    		A=num[A].fa;
    	}
    	return 1;
    }

--------------------

#### 实现代码 ####

#include<bits/stdc++.h>
    using namespace std;
    
    struct node{ 
    	string fa;
    	int sex;
    };
    
    map <string, node> num;
     
    //判断 s1 是否为 s2 的嫡系
    bool judge1(string s1, string s2){ 
    	for(string A=s1; !A.empty(); A=num[A].fa)
    		if(A==s2) return false;
    	return true;
    }
    
    //s1与s2五代以内无有公共祖先 
    bool judge2(string s1, string s2){ 
    	int i=1;
    	string A, B;
    	for(A=s1; !A.empty()&&i<=5; i++){ 
    		int j=1;
    		for(B=s2; !B.empty()&&j<=5; j++){ 
    			if(A==B&&(i<5||j<5))
    				return 0;
    			B=num[B].fa;
    		}
    		A=num[A].fa;
    	}
    	return 1;
    }
    
    int main(){ 
    	int n, k;
    	scanf("%d", &n);
    	for(int i=0; i<n; i++){ 
    		string m, x;
    		cin>>m>>x;
    		//判断性别
    		switch(x[x.size()-1]){ 
    			case 'm': num[m].sex = 'm';
    					break;
    			case 'f': num[m].sex = 'f';
    					break;
    			case 'n': num[m].fa = x.substr(0, x.size()-4);
    					num[m].sex = 'm';
    					break;
    			case 'r': num[m].fa = x.substr(0, x.size()-7);
    					num[m].sex = 'f';
    					break;
    		}
    	}
    	
    	cin>>k;
    	for(int i=0; i<k; i++){ 
    		string m1, x1, m2, x2;
    		cin>>m1>>x1>>m2>>x2;
    		if(num.find(m1)==num.end()||num.find(m2)==num.end())
    			cout<<"NA\n";
    		else if(num[m1].sex==num[m2].sex)
    			cout<<"Whatever\n";
    		else{ 
    			if(judge1(m1, m2)&&judge1(m2, m1)&&judge2(m1, m2))
    				cout<<"Yes\n";
    			else
    				cout<<"No\n";
    		}
    	}
    	
    	return 0;
    }

### 总结 ###

看了网上一些代码，并没有将全部情况都考虑到，但判题时能够通过全部样例，就很神奇。  
比赛期间尽管提交，能混到分的话，就很妙…

[Link 1]: https://blog.csdn.net/Zhengyangxinn/article/details/110183324
[Link 2]: https://blog.csdn.net/Zhengyangxinn/article/details/110201735
[t1]: /images/20221120/91bb09ba9be340de9c61e26af1ad83c6.png
[t2]: https://img-blog.csdnimg.cn/2020112716370494.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[t3]: https://img-blog.csdnimg.cn/20201127163733233.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70