pta 习题集5-17 家谱处理

人类学研究对于家族很感兴趣,于是研究人员搜集了一些家族的家谱进行研究。实验中,使用计算机处理家谱。为了实现这个目的,研究人员将家谱转换为文本文件。下面为家谱文本文件的实例:

John
  Robert
    Frank
    Andrew
  Nancy
    David

家谱文本文件中,每一行包含一个人的名字。第一行中的名字是这个家族最早的祖先。家谱仅包含最早祖先的后代,而他们的丈夫或妻子不出现在家谱中。每个人的子女比父母多缩进2个空格。以上述家谱文本文件为例,John这个家族最早的祖先,他有两个子女RobertNancyRobert有两个子女FrankAndrewNancy只有一个子女David

在实验中,研究人员还收集了家庭文件,并提取了家谱中有关两个人关系的陈述语句。下面为家谱中关系的陈述语句实例:

John is the parent of Robert
Robert is a sibling of Nancy
David is a descendant of Robert

研究人员需要判断每个陈述语句是真还是假,请编写程序帮助研究人员判断。

输入格式:

输入首先给出2个正整数NN(2≤N≤1002≤N≤100)和MM(≤100≤100),其中NN为家谱中名字的数量,MM为家谱中陈述语句的数量,输入的每行不超过70个字符。

名字的字符串由不超过10个英文字母组成。在家谱中的第一行给出的名字前没有缩进空格。家谱中的其他名字至少缩进2个空格,即他们是家谱中最早祖先(第一行给出的名字)的后代,且如果家谱中一个名字前缩进kk个空格,则下一行中名字至多缩进k+2k+2个空格。

在一个家谱中同样的名字不会出现两次,且家谱中没有出现的名字不会出现在陈述语句中。每句陈述语句格式如下,其中XY为家谱中的不同名字:

X is a child of Y
X is the parent of Y
X is a sibling of Y
X is a descendant of Y
X is an ancestor of Y

输出格式:

对于测试用例中的每句陈述语句,在一行中输出True,如果陈述为真,或False,如果陈述为假。

输入样例:

6 5
John
Robert
    Frank
    Andrew
  Nancy
    David
Robert is a child of John
Robert is an ancestor of Andrew
Robert is a sibling of Nancy
Nancy is the parent of Frank
John is a descendant of Andrew

输出样例:

True
True
True
False
False
#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <map>

using namespace std;
int n,m;
char b[105];
map<string,int> a;
int f[105];
string s;
int num[105];
int main()
{
    scanf("%d%d\n",&n,&m);
    int cnt=0;
    memset(num,0,sizeof(num));
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        gets(b);
        s="";
        for(int j=0;b[j]!='\0';j++)
        {
            if(b[j]==' ')
                num[i]++;
            else
                s+=b[j];
        }
        a[s]=++cnt;
        for(int k=i-1;k>=1;k--)
        {
            if(num[i]==num[k])
            {
                f[i]=f[k];
                break;
            }

            if(num[i]==(num[k]+2))
            {
                f[i]=k;
                break;
            }
        }
    }
    string x="",y="",z="";
    for(int i=1;i<=m;i++)
    {
        x="";y="";z="";
        gets(b);
        int tag=1;
        for(int j=0;b[j]!='\0';j++)
        {
            if(b[j]==' ')
            {
                tag++;
                continue;
            }
            if(tag==1)
                x+=b[j];
            else if(tag==6)
                y+=b[j];
            else if(tag==4)
            {
                z+=b[j];
            }
        }
        int ans=0;
        int fx=a[x];int fy=a[y];
        if(z.find("c")==0)
        {
            if(f[fx]==fy)
                ans=1;
        }
        else if(z.find("a")==0)
        {
            while(fy!=0)
            {
                if(fx==f[fy])
                {
                   ans=1;
                    break;
                }
                fy=f[fy];
            }

        }
        else if(z.find("s")==0)
        {
            if(f[fx]==f[fy])
                ans=1;
        }
        else if(z.find("p")==0)
        {
            if(f[fy]==fx)
                ans=1;
        }
        else if(z.find("d")==0)
        {
            while(fx!=0)
            {
                if(fy==f[fx])
                {
                    ans=1;
                    break;
                }
                fx=f[fx];
            }

        }
        if(!ans)
            printf("False\n");
        else
            printf("True\n");
        
        
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

【学习】《R实战》读书笔记(第五章)

读书会是一种在于拓展视野、宏观思维、知识交流、提升生活的活动。PPV课R语言读书会以“学习、分享、进步”为宗旨,通过成员协作完成R语言专业书籍的精读和分享,达到...

51290
来自专栏数据结构与算法

UOJ#386. 【UNR #3】鸽子固定器(链表)

如果我们按$s$排序后,我们就可以枚举$max  \ s_i$和$min \ s_i$

11710
来自专栏大数据挖掘DT机器学习

【手把手教你做项目】自然语言处理:单词抽取/统计

作者 白宁超 成都信息工程大学硕士。 近期关注数据分析统计学、机器学习。 原文:http://www.cnblogs.com/baiboy/p/zryy1.h...

360130
来自专栏WOLFRAM

九宫格数独游戏

26180
来自专栏大数据挖掘DT机器学习

【手把手教你做项目】自然语言处理:单词抽取/统计

作者 白宁超 成都信息工程大学硕士。 近期关注数据分析统计学、机器学习。 原文:http://www.cnblogs.com/baiboy/p/zryy1.ht...

34050
来自专栏WOLFRAM

用 Wolfram 语言来做2017年高考数学试题之天津理科卷

19240
来自专栏机器学习入门

挑战程序竞赛系列(80):4.3 2-SAT(4)

挑战程序竞赛系列(80):4.3 2-SAT(4) 传送门:POJ 2749: Building roads 题意: 阳关路与独木桥:有N个农场,其中A对相...

23890
来自专栏数据结构与算法

1163 访问艺术馆

 时间限制: 1 s  空间限制: 128000 KB  题目等级 : 大师 Master 题解  查看运行结果 题目描述 Description     皮尔...

28970
来自专栏WOLFRAM

Mathematica 迷中智 | 奥运五环 数字谜题

18120
来自专栏落影的专栏

程序员进阶之算法练习(十八)

前言 最近在接触新知识,也是选择2017年的方向。 其他文集更新会放缓,没有学习就没有心得,肚中无墨就无从下笔。 但是算法练习还是挺好玩的,欢迎关注algo...

35850

扫码关注云+社区

领取腾讯云代金券