A16634. Merging the Sets
编程题
普及-
知识点
题目描述
给你 $n$ 个集合 $S_1, S_2, \ldots, S_n$，其中每个集合里的元素是 $1$ 到 $m$ 之间的整数。
你需要选择一些集合（可以一个都不选，也可以全选），使得从 $1$ 到 $m$ 的每个整数至少在一个被选中的集合中出现。
请判断是否有至少三种不同的方式选择集合，使上述条件成立。
你需要选择一些集合（可以一个都不选，也可以全选），使得从 $1$ 到 $m$ 的每个整数至少在一个被选中的集合中出现。
请判断是否有至少三种不同的方式选择集合，使上述条件成立。
输入格式
每组测试数据包含多组测试用例。第一行为测试用例组数 $t$（$1 \le t \le 10^4$）。接下来是各组测试数据。
每个测试用例的第一行为两个整数 $n$ 和 $m$（$2 \leq n \leq 5 \cdot 10^4$，$1 \le m \leq 10^5$），分别表示集合数和整数范围上界。
接下来有 $n$ 行，第 $i$ 行首先包含一个整数 $l_i$（$1\le l_i \le m$），表示第 $i$ 个集合的大小。
接下来一行有 $l_i$ 个整数 $S_{i,1}, S_{i,2}, \ldots, S_{i, l_i}$（$1\le S_{i,1} < S_{i,2} < \cdots < S_{i, l_i} \le m$），表示 $S_i$ 的元素。
记 $L=\sum\limits_{i=1}^n l_i$。保证：
- 所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^4$；
- 所有测试用例中 $m$ 的总和不超过 $10^5$；
- 所有测试用例中 $L$ 的总和不超过 $2 \cdot 10^5$。
每个测试用例的第一行为两个整数 $n$ 和 $m$（$2 \leq n \leq 5 \cdot 10^4$，$1 \le m \leq 10^5$），分别表示集合数和整数范围上界。
接下来有 $n$ 行，第 $i$ 行首先包含一个整数 $l_i$（$1\le l_i \le m$），表示第 $i$ 个集合的大小。
接下来一行有 $l_i$ 个整数 $S_{i,1}, S_{i,2}, \ldots, S_{i, l_i}$（$1\le S_{i,1} < S_{i,2} < \cdots < S_{i, l_i} \le m$），表示 $S_i$ 的元素。
记 $L=\sum\limits_{i=1}^n l_i$。保证：
- 所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^4$；
- 所有测试用例中 $m$ 的总和不超过 $10^5$；
- 所有测试用例中 $L$ 的总和不超过 $2 \cdot 10^5$。
输出格式
对于每个测试用例，如果存在至少三种不同的选择集合的方案，输出
你的答案可以用大小写任意的形式输出，如 “yEs”，"yes"，"Yes" 和 "YES" 都会被认为是正解。
YES，否则输出 NO。你的答案可以用大小写任意的形式输出，如 “yEs”，"yes"，"Yes" 和 "YES" 都会被认为是正解。
输入输出样例
输入 #1
6 3 2 2 1 2 1 1 1 2 4 10 3 1 2 3 2 4 5 1 6 4 7 8 9 10 2 5 4 1 2 3 4 4 1 2 3 4 5 5 5 1 2 3 4 5 5 1 2 3 4 5 5 1 2 3 4 5 5 1 2 3 4 5 5 1 2 3 4 5 5 10 4 1 2 3 4 5 1 2 5 6 7 5 2 6 7 8 9 4 6 7 8 9 2 9 10 5 5 1 1 1 2 1 3 2 4 5 1 5
输出 #1
YES NO NO YES YES NO
说明/提示
在第一个测试用例中，存在 $5 \ge 3$ 种选择方案：
- 只选 $S_1$ — $1$ 和 $2$ 都包含在 $S_1$ 中；
- 选 $S_1$ 和 $S_2$ — $1$ 包含在 $S_1$ 和 $S_2$，$2$ 包含在 $S_1$；
- 选 $S_1$ 和 $S_3$ — $1$ 包含在 $S_1$，$2$ 包含在 $S_1$ 和 $S_3$；
- 选 $S_2$ 和 $S_3$ — $1$ 包含在 $S_2$，$2$ 包含在 $S_3$；
- 选 $S_1$、$S_2$ 和 $S_3$ — $1$ 包含在 $S_1$ 和 $S_2$，$2$ 包含在 $S_1$ 和 $S_3$。
注意，单独选 $S_2$ 是不合法的，因为 $2$ 不包含在 $S_2$ 中。
在第二个测试用例中，只有唯一的一种方式就是全部选上所有集合。
在第三个测试用例中，$5$ 没有出现在任意一个集合中，因此无法选择满足条件的集合。
在第四个测试用例中，任选非空的集合组合都满足条件，所以方案数为 $2^5-1=31\ge3$。
- 只选 $S_1$ — $1$ 和 $2$ 都包含在 $S_1$ 中；
- 选 $S_1$ 和 $S_2$ — $1$ 包含在 $S_1$ 和 $S_2$，$2$ 包含在 $S_1$；
- 选 $S_1$ 和 $S_3$ — $1$ 包含在 $S_1$，$2$ 包含在 $S_1$ 和 $S_3$；
- 选 $S_2$ 和 $S_3$ — $1$ 包含在 $S_2$，$2$ 包含在 $S_3$；
- 选 $S_1$、$S_2$ 和 $S_3$ — $1$ 包含在 $S_1$ 和 $S_2$，$2$ 包含在 $S_1$ 和 $S_3$。
注意，单独选 $S_2$ 是不合法的，因为 $2$ 不包含在 $S_2$ 中。
在第二个测试用例中，只有唯一的一种方式就是全部选上所有集合。
在第三个测试用例中，$5$ 没有出现在任意一个集合中，因此无法选择满足条件的集合。
在第四个测试用例中，任选非空的集合组合都满足条件，所以方案数为 $2^5-1=31\ge3$。