题解：P1701 [USACO19OPEN] Cow Evolution B

· · 题解

P1701 [USACO19OPEN] Cow Evolution B 题解

思路分析

先换个角度看问题，对于每一种特性，记录哪些子种群拥有它。例如，特性 flying 出现在第 2,3,5 个子种群中，就把它记成集合 \{2,3,5\}。

一种特性只出现一次，所以拥有这种特性的奶牛一定集中在进化树的某一根树枝下面，不可能东一块、西一块。

那么拿出任意两种特性来比较，它们只能有下面三种关系：

  1. 没有子种群同时拥有这两种特性；
  2. 拥有第一种特性的子种群，全都拥有第二种特性；
  3. 拥有第二种特性的子种群，全都拥有第一种特性。

用集合表示，就是两个集合要么完全分开，要么一个被另一个包含。

所以做法很简单：枚举任意两种特性，只要发现它们有一部分重合，但谁也不完全包含谁，就输出 no。如果所有特性都没有这种冲突，就输出 yes。

参考代码

#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

const int N = 35, M = 635;

int n, cnt, a[M];
string s;
map<string, int> m;

int main() {
    scanf("%d", &n);
    for (int i = 0, x; i < n; ++i) {
        scanf("%d", &x);
        for (int j = 0; j < x; ++j) {
            cin >> s;
            if (!m.count(s)) m[s] = ++cnt;
            a[m[s]] |= 1 << i;
        }
    }

    for (int i = 1; i <= cnt; ++i) {
        for (int j = i + 1; j <= cnt; ++j) {
            int t = a[i] & a[j];
            if (t && t != a[i] && t != a[j]) {
                puts("no");
                return 0;
            }
        }
    }
    puts("yes");

    return 0;
}