天梯题集——冰岛人（隐藏条件：考虑嫡系）-蒲公英云

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

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

前文

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

冰岛人

解题难点

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

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;
}