石景山上海网站建设软件商店电脑版下载

石景山上海网站建设,软件商店电脑版下载,创建个人网站,模板网站怎么建设优化题目分析 本题要求根据输入的父子关系对#xff08;child-parent pairs\texttt{child-parent pairs}child-parent pairs#xff09;构建一个家族树#xff0c;然后对一系列查询对#xff08;query pairs\texttt{query pairs}query pairs#xff09;判断两人之间的亲属关系…题目分析本题要求根据输入的父子关系对child-parent pairs\texttt{child-parent pairs}child-parent pairs构建一个家族树然后对一系列查询对query pairs\texttt{query pairs}query pairs判断两人之间的亲属关系并按照特定格式输出。关系包括直接父子、祖孙、兄弟姐妹、堂表亲等。关键定义ppp是qqq的kkk-descendent\texttt{descendent}descendentkkk-ancestor\texttt{ancestor}ancestor当且仅当存在一条长度为kkk的父子链。关系分类child / parent\texttt{child / parent}child / parent直接父子k0k0k0grand child/parent\texttt{grand child/parent}grand child/parentk1k1k1great grand child/parent\texttt{great grand child/parent}great grand child/parentk≥2k \ge 2k≥2前缀great\texttt{great}great重复k−1k-1k−1次。sibling\texttt{sibling}sibling共享同一父母即000代表000次removed\texttt{removed}removed的000-th cousin\texttt{th cousin}th cousin。cousin\texttt{cousin}cousin设ppp和qqq的最小公共祖先为rrrppp是rrr的mmm-descendent\texttt{descendent}descendentqqq是rrr的nnn-descendent\texttt{descendent}descendent则他们是kkk-th cousin\texttt{th cousin}th cousin其中kmin⁡(m,n)k \min(m, n)kmin(m,n)。removed\texttt{removed}removedjjj次其中j∣m−n∣j |m - n|j∣m−n∣。no relation\texttt{no relation}no relation不在同一家族树中。输入限制最多300300300个不同名字名字长度不超过303030。最多100100100个查询对。无循环关系。输出要求按格式输出关系若removed\texttt{removed}removed次数为000则不输出removed 0。数字后不加序数后缀如st,nd,rd,th。解题思路本题虽然名为“树”但不需要显式建树只需维护每个节点的父节点映射即可。由于名字是字符串我们使用mapstring, int将名字映射为整数编号便于处理。步骤读取父子关系每行读入child\texttt{child}child和parent\texttt{parent}parent直到遇到no.child no.parent。为新名字分配编号记录parent[child] parent。处理查询对每个查询对(p,q)(p, q)(p,q)检查是否存在若任一名字不在映射中输出no relation。检查是否在同一棵树分别找到ppp和qqq的根祖先不断找父节点直到DUMMY若不同则输出no relation。判断直接关系若ppp是qqq的祖先根据深度输出parent / grand parent / great ... grand parent\texttt{parent / grand parent / great ... grand parent}parent / grand parent / great ... grand parent。若ppp是qqq的后代根据深度输出child / grand child / great ... grand child\texttt{child / grand child / great ... grand child}child / grand child / great ... grand child。若ppp和qqq是兄弟姐妹同一父母输出sibling。判断堂表亲关系先计算ppp和qqq到根节点的深度mmm和nnn。将ppp和qqq提升到同一深度然后同时向上找直到找到同一父母。计算kmin⁡(m′,n′)k \min(m, n)kmin(m′,n′)提升后剩余深度j∣m−n∣j |m - n|j∣m−n∣深度差。输出k cousin若j0j0j0或k cousin removed j。注意题目要求removed\texttt{removed}removed为000时不输出removed 0且数字后不加序数词。代码// Climbing Trees// UVa ID: 115// Verdict: Accepted// Submission Date: 2011-11-27// UVa Run Time: 0.008s//// 版权所有C2011邱秋。metaphysis # yeah dot net//// [解题方法]// 模拟题。由于只需要保存父子关系不一定要构建树。虽然方法是直接的但是有点繁琐。#includebits/stdc.husingnamespacestd;#defineMAXN310#defineDUMMY(-1)intparent[MAXN];mapstring,intgenealogy;boolisAncestor(string fName,string sName){intnFirstgenealogy[fName];intnSecondgenealogy[sName];intdepth0;boolfoundfalse;while(parent[nSecond]!DUMMY){if(parent[nSecond]nFirst){foundtrue;break;}nSecondparent[nSecond];depth;}if(found){if(depth0)coutparent\n;elseif(depth1)coutgrand parent\n;else{for(inti1;idepth;i)coutgreat ;coutgrand parent\n;}returntrue;}returnfalse;}boolisDescendent(string fName,string sName){intnFirstgenealogy[fName];intnSecondgenealogy[sName];intdepth0;boolfoundfalse;while(parent[nFirst]!DUMMY){if(parent[nFirst]nSecond){foundtrue;break;}nFirstparent[nFirst];depth;}if(found){if(depth0)coutchild\n;elseif(depth1)coutgrand child\n;else{for(inti1;idepth;i)coutgreat ;coutgrand child\n;}returntrue;}returnfalse;}boolisInTree(string fName,string sName){if(genealogy.find(fName)genealogy.end()||genealogy.find(sName)genealogy.end()){coutno relation\n;returnfalse;}returntrue;}boolisInSameTree(string fName,string sName){intnFirstgenealogy[fName];intnSecondgenealogy[sName];while(parent[nFirst]!DUMMY)nFirstparent[nFirst];while(parent[nSecond]!DUMMY)nSecondparent[nSecond];if(nFirst!nSecond){coutno relation\n;returnfalse;}returntrue;}boolisSibling(string fName,string sName){intnFirstgenealogy[fName];intnSecondgenealogy[sName];if(parent[nFirst]!DUMMYparent[nSecond]!DUMMYparent[nFirst]parent[nSecond]){coutsibling\n;returntrue;}returnfalse;}boolisCousin(string fName,string sName){intnFirstgenealogy[fName];intnSecondgenealogy[sName];intn0,m0;while(parent[nFirst]!DUMMY){nFirstparent[nFirst];n;}while(parent[nSecond]!DUMMY){nSecondparent[nSecond];m;}nFirstgenealogy[fName];nSecondgenealogy[sName];intbackNn,backMm;if(nm){while(nm){nFirstparent[nFirst];n--;}while(parent[nFirst]!parent[nSecond]){nFirstparent[nFirst];nSecondparent[nSecond];n--;}backN-n;backM-n;coutbackM cousin removed (backN-backM)\n;}elseif(mn){while(mn){nSecondparent[nSecond];m--;}while(parent[nFirst]!parent[nSecond]){nFirstparent[nFirst];nSecondparent[nSecond];m--;}backN-m;backM-m;coutbackN cousin removed (backM-backN)\n;}else{while(parent[nFirst]!parent[nSecond]){nFirstparent[nFirst];nSecondparent[nSecond];n--;m--;}cout(backN-n) cousin\n;}returntrue;}intmain(intargc,charconst*argv[]){intnNames0;string allNames[MAXN];string childName,parentName;for(inti0;iMAXN;i)parent[i]DUMMY;while(cinchildNameparentName){if(childNameno.childparentNameno.parent)break;if(genealogy.find(childName)genealogy.end()){genealogy[childName]nNames;allNames[nNames]childName;}if(genealogy.find(parentName)genealogy.end()){genealogy[parentName]nNames;allNames[nNames]parentName;}parent[genealogy[childName]]genealogy[parentName];}while(cinchildNameparentName){if(!isInTree(childName,parentName))continue;if(!isInSameTree(childName,parentName))continue;if(isAncestor(childName,parentName))continue;if(isDescendent(childName,parentName))continue;if(isSibling(childName,parentName))continue;if(isCousin(childName,parentName))continue;}return0;}复杂度分析每次查询需要向上遍历祖先链最坏深度为O(N)O(N)O(N)NNN为节点数≤300\le 300≤300。总查询次数≤100\le 100≤100因此总时间复杂度为O(N⋅Q)O(N \cdot Q)O(N⋅Q)完全可行。本题关键在于理清亲属关系的定义并仔细实现各种情况的判断与输出格式。