自己的网站,克州建设工程信息网,无广告自助建站,中国纪检监察报总编一#xff1a;题目
人类学研究对于家族很感兴趣#xff0c;于是研究人员搜集了一些家族的家谱进行研究。实验中#xff0c;使用计算机处理家谱。为了实现这个目的#xff0c;研究人员将家谱转换为文本文件。下面为家谱文本文件的实例#xff1a;
John Robert Frank Andr…一题目
人类学研究对于家族很感兴趣于是研究人员搜集了一些家族的家谱进行研究。实验中使用计算机处理家谱。为了实现这个目的研究人员将家谱转换为文本文件。下面为家谱文本文件的实例
John Robert Frank Andrew Nancy David 家谱文本文件中每一行包含一个人的名字。第一行中的名字是这个家族最早的祖先。家谱仅包含最早祖先的后代而他们的丈夫或妻子不出现在家谱中。每个人的子女比父母多缩进2个空格。以上述家谱文本文件为例John这个家族最早的祖先他有两个子女Robert和NancyRobert有两个子女Frank和AndrewNancy只有一个子女David。
在实验中研究人员还收集了家庭文件并提取了家谱中有关两个人关系的陈述语句。下面为家谱中关系的陈述语句实例
John is the parent of Robert Robert is a sibling of Nancy David is a descendant of Robert 研究人员需要判断每个陈述语句是真还是假请编写程序帮助研究人员判断。
输入格式: 输入首先给出2个正整数N2≤N≤100和M≤100其中N为家谱中名字的数量M为家谱中陈述语句的数量输入的每行不超过70个字符。
名字的字符串由不超过10个英文字母组成。在家谱中的第一行给出的名字前没有缩进空格。家谱中的其他名字至少缩进2个空格即他们是家谱中最早祖先第一行给出的名字的后代且如果家谱中一个名字前缩进k个空格则下一行中名字至多缩进k2个空格。
在一个家谱中同样的名字不会出现两次且家谱中没有出现的名字不会出现在陈述语句中。每句陈述语句格式如下其中X和Y为家谱中的不同名字
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
二思路
用map容器记录空格再用一个map来记录关系 思路分析 第一步 x是y的孩子--------- y比x多两个空格 x是y的父母--------- x比y少两个空格 x是y的兄弟姐妹----- 空格数相等 x是y的后代--------- 只要x的空格数比y 多就可以 x是y的祖先--------- y比x多的空格数 大于等于2 第二步 考虑 关系 代码当中有解释 很炫的
三上码
//思路分析
//第一步
//x是y的孩子--------- y比x多两个空格
//x是y的父母--------- x比y少两个空格
//x是y的兄弟姐妹----- 空格数相等
//x是y的后代--------- 只要x的空格数比y 多就可以
//x是y的祖先--------- y比x多的空格数 大于等于2 //第二步
//考虑 关系
//
//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#includebits/stdc.h
using namespace std;mapstring,stringfather;//存关系 father[孩子] 双亲 int spaceNum(string str,int cnt){ //计算空格数 for( int i 0; i str.size(); i ){if(str[i] )cnt;}return cnt;
}int judgment(string str1,string str2){ //往上找爹 用于解决测试点三 while( father[str1] ! str2 ){if(father[str1] zuxian)break;string temp;temp father[str1]; str1 temp;}if(father[str1] str2 )return 1;elsereturn 0;
}int main()
{mapstring,intm; mapstring,int:: iterator t;vectorstringv(110);//存名字 int N,M;cin N M;getchar();//出去换行符的干扰 for( int i 0; i N; i ){string str;getline(cin,str);int count spaceNum(str,0);if( count 0 ){father[str] zuxian;v[0] str; //如果不给容器的大小 即vectorstringv(N); 则需要用v.push_back(); // v.push_back(str); }else{string str1 str.substr(count);//这里为截取字符串 将空格去掉 m[str1] count;//这里count 可能会重复 但没关系map当中不存在键值重复存在关键值重复father[str1] v[count/2 -1]; //这里非常巧妙学大佬的 因为孩子的空个数总是比双亲少两个 count/2-1这样 就 可 以 将 双亲和孩子yiyi对应上 v[count/2] str1; //当空格数相等时会发生覆盖 } } for( int i 0; i M; i ){string a,b,c,d,e,f;cin a b c d e f;if( d child ){if(m[a] - m[f] 2 father[a] f)// father[a] f a的双亲是f cout True endl;elsecout False endl;}if( d parent ){if(m[f] - m[a] 2 father[f] a)cout True endl;elsecout False endl; } if( d sibling ){if(m[a] - m[f] 0 father[a] father[f])cout True endl;elsecout False endl; } if( d descendant ){int a1 judgment(a,f); if( (m[a] - m[f] 2 a1 1) || father[f] zuxian ) //如果这里的f是祖先的话 任何他的孩子 都是后代 cout True endl;elsecout False endl; }if( d ancestor ) {int a1 judgment(f,a); if((m[f] - m[a] 2 a1 1) || father[a] zuxian )cout True endl;elsecout False endl; }}}//6 1
//John
// Robert
// Frank
// Andrew
// Nancy
// David
//John is a descendant of Andrew 四总结
肝了5个小时 觉得值得 加油陌生人
