Cow Evolution 题解

现在是3019年，在过去的一千年里发生了不计其数的牛类进化，产生了具有各种有趣特性的奶牛。

牛类进化的记录可以用一棵树来表示，起源是位于树根位置的没有特殊特性的奶牛。树上每一个产生后代的结点，有可能所有的奶牛都进化出了一种新的特性（比如说喷火（fire breathing），如下图所示，其中所有斑点（spots）奶牛最后都能喷火），或者是奶牛种群产生了分支进化，其中有些进化出了新的特性（比如，飞（flying）），有的没有。

树底部的叶结点表示3019年所有产生的奶牛的子种群。没有不同的叶结点（子种群）具有完全相同的一组特性。例如，子种群#1是没有特殊特性的奶牛，子种群#3是能够心灵感应的（telepathic）并且会飞的奶牛。相比之下，子种群#2是会飞但不能心灵感应的奶牛。子种群#3是唯一既会飞又会心灵感应的。

像上图这样每一种进化出的新特性都恰好在树中的一条边上产生（也就是说，在整个进化历史中仅在一个时间点产生），这样的进化树被称为是“合法的”。例如，如果斑点这一特性在两个不同分支中均进化产生，这棵进化树就不是合法的。给定3019年奶牛子种群的描述，请判断是否这可以由一棵合法的进化树所解释。

输入

输入的第一行包含子种群的数量N（2≤N≤25）。以下N行每行描述一个子种群。每行包含一个整数K（0≤K≤25），之后是K个该子种群奶牛所拥有的特性。特性是由至多20个小写字母（a…z）组成的字符串。没有两个子种群拥有完全相同的特性。

输出

如果可能构造一棵可以解释所有子种群产生途径的进化树，输出"yes"，否则输出"no"。

样例输入

4
2 spots firebreathing
0
1 flying
2 telepathic flying

样例输出

yes

数据范围限制

2≤N≤25
0≤K≤25

题目大意：

我以前很少在博客写题目大意，可这题是有点难懂，所以讲一下。
题目讲了给出n个具有若干个（或没有）特性的叶子节点，求这些叶子节点是否有具有同一个也根节点。对于每一个结点，它能有无线条分支，每条分支可进化出的一个新特性（或不进化）。 并且每一个子节点都遗传了它父亲节点的全部特性，每个分支都是独一无二的，firebreathing这种特性进化只有可能从一种生物进化而成（这句话的意思是有同一特性的叶子节点必有同样的祖先） 。

题解：

想法：

这道题算是一道数学题，要我们证明同一特性的叶子节点必有同样的祖先这一 结论_ 1，如果成立那就输出“yes”，否则就“no”。我们先设这一特性成立，那么就又得出一个结论_2——特性完全不同的叶子节点必有不同的祖先。再根据这个结论枚举任意两种 特性所拥有子节点 （题目中给的是子节点所拥有特性，所以我们要转换，并将特性字符串改成数字不用在意顺序），会有三种情况，一是没子节点重叠，不用理会，因为这两个不同性质成功分成两个不同的结点中；二是子节点完全重叠，并且多数覆盖少数，也不用理会，因为这两个不同性质成功分成一个相同的结点中；三是子节点重叠，并且两者没完全覆盖，这种情况就有违背于上没的结论，就输出“no”，因为重叠部分满足结论_1，而双方未重叠部分又满足结论_2，矛盾。

实现：

想法清楚后，再来看看如果实现。

实现代码有两个难点， 一是转换“子节点所拥有特性”为“特性所拥有子节点”;二是那三种情况的实现 在这里我就上第二个难点的核心代码给大家参考：

for(int i=1;i<=bj[0][0];i++){for(int j=1;j<=bj[0][0];j++){//任意两种特性所拥有子节点if(i!=j){int o;if(b[i][0]>b[j][0])o=i;else o=j;int js=0,js1=0;//js表示重叠了几个，js1表示是否重叠for(int k=1;k<=b[o][0];k++){for(int l=1;l<=b[i+j-o][0];l++){if(b[o][k]==b[i+j-o][l]){js++;js1=1;break;}}}if(js1==1&&js<b[i+j-o][0]){//重叠了并且两者没完全覆盖printf("no");//矛盾，输出“no”return 0;}}}
}
printf("yes");//证明不可能不成立，代表成立；