📅 发布时间：2026/6/20 22:13:03

CF2146B Merging the Sets

📄 CF2146B Merging the Sets 题解

题目大意

给定 $n$ 个集合 $S_1, \ldots, S_n$，元素范围是 1 到 $m$。你需要判断，是否存在至少 3 种不同的选择集合的方式（可以选择 0 个或多个集合），使得所选集合的并集包含从 1 到 $m$ 的所有整数。

💡 思路分析

这道题问的是方案数是否 $\ge 3$。直接去“构造”所有方案会很复杂。我们可以换一个角度，从一个已知的解出发，去寻找其他的解。

这个思路我们称之为**“移除法”**。

第一步：检查“全选”是否为合法解

一个最容易检查的方案就是把所有 $n$ 个集合都选上（我们称之为 $All$）。

要检查 $All$ 是否合法，我们只需要知道 $All$ 是否覆盖了 $1$ 到 $m$ 的所有整数。

我们使用一个数组 counts[m+1] 来统计每个数字 $i$（$1 \le i \le m$）在所有 $n$ 个集合中总共出现了多少次。
在读入所有数据的同时，我们可以填充这个 counts 数组。
读入完毕后，遍历 counts 数组（从 $i=1$ 到 $m$）：
- 如果存在任何一个 counts[i] == 0，这意味着数字 $i$ 从未出现过。
- 此时，连“全选”都无法覆盖 $i$，说明没有任何方案能覆盖所有数字。
- 总方案数为 0。我们直接输出 NO，并结束当前测试用例。
如果循环结束后，发现所有的 counts[i] 都 $\ge 1$，这说明“全选”$All$ 是一个合法的解。
我们就把 $All$ 当作我们找到的第 1 种合法方案。

第二步：寻找其他解（“移除法”）

既然 $All$ 是一个解，那么 $All$ 的子集有没有可能也是解？

最简单的子集就是“全选”再去掉一个集合 $S_i$，我们记为 $All \setminus {S_i}$。

问题：$All \setminus {S_i}$ 什么时候是合法的解？
答案：当 $S_i$ 是一个**“可移除的”**（或“冗余的”）集合时。

第三步：定义“可移除的”集合

一个集合 $S_i$ 是“可移除的”，当且仅当：
$S_i$ 中包含的每一个元素 $x$，在 $S_i$ 之外至少还被其他一个集合包含。

这个定义听起来有点绕，但用我们第一步的 counts 数组来描述就非常简单：

$S_i$ 是“可移除的” $\iff$ 对于 $S_i$ 中的所有元素 $x$，都有 counts[x] >= 2。

如果 $S_i$ 中有任何一个元素 $x$ 满足 counts[x] == 1，说明 $x$ 只在 $S_i$ 中出现过。
如果此时移除了 $S_i$，数字 $x$ 就无法被覆盖了。
因此，这个 $S_i$ 就是“不可移除的”（或“必要的”）。

第四步：统计与结论

现在我们的目标很明确：统计有多少个“可移除的”集合。

我们需要一个二维向量（比如 vector<vector<int>> sets）来存储所有 $n$ 个集合的元素，以便我们能回头遍历它们。
初始化 removable_count = 0。
遍历所有 $n$ 个集合（i 从 0 到 $n-1$）：
- 对于第 $i$ 个集合 sets[i]，假设它是可移除的（bool can_remove = true）。
- 遍历 sets[i] 中的每一个元素 $x$：
  - if (counts[x] == 1)：
    - 说明 $S_i$ 是 $x$ 的唯一来源， $S_i$ 不可移除。
    - 设置 can_remove = false。
    - break（跳出内层循环，没必要再检查 $S_i$ 的其他元素了）。
- 如果内层循环正常结束，can_remove 仍然是 true，说明 sets[i] 中所有元素 $x$ 都有 counts[x] >= 2。
- 此时 removable_count++。
在外层循环结束后，我们就得到了“可移除”集合的总数 removable_count。现在来判断答案：
- Case 1: removable_count == 0
  - 说明每个集合都是“必要的”，缺一不可。
  - 总共只有 1 种方案：$All$（“全选”）。
  - $1 < 3$，输出 NO。
- Case 2: removable_count == 1
  - 说明只有一个集合 $S_k$ 是可移除的。
  - 总共只有 2 种方案：
    1. $All$
    2. $All \setminus {S_k}$ （去掉 $S_k$）
  - $2 < 3$，输出 NO。
- Case 3: removable_count >= 2
  - 说明至少有两个不同的集合 $S_i$ 和 $S_j$ 是可移除的。
  - 这至少给我们提供了 3 种不同的方案：
    1. $All$
    2. $All \setminus {S_i}$ （去掉 $S_i$）
    3. $All \setminus {S_j}$ （去掉 $S_j$）
  - （可能还有 $All \setminus {S_i, S_j}$ 等更多方案，但我们不关心）
  - $3 \ge 3$，输出 YES。

🚀 复杂度分析

时间复杂度： $O(n + m + L)$。
- $L$ 是所有集合的元素总数（$L = \sum l_i$）。
- 读入数据并存入 counts 和 sets：$O(L)$。
- 检查 $All$ 是否可行：$O(m)$。
- 统计可移除集合：外层循环 $n$ 次，内层循环 $l_i$ 次，总共是 $\sum l_i = L$ 次。
- 总时间为 $O(n + m + L)$。根据题目的总和限制（$\sum L \le 2 \cdot 10^5$），这个复杂度非常快，不会 TLE。
空间复杂度： $O(n + m + L)$。
- counts 数组占用 $O(m)$。
- sets 向量占用 $O(n)$（存储 $n$ 个向量对象）和 $O(L)$（存储 $L$ 个元素）。
- 总空间为 $O(n + m + L)$。根据总和限制，内存占用很小，不会 MLE。

💻 AC 代码

#include<bits/stdc++.h>
using namespace std;int main() {int t;cin >> t;while(t--) {int n, m;cin >> n >> m;// 1. 计数 // counts 用于统计 1 到 m 每个数字出现的总次数vector<int> counts(m + 1, 0);// sets 用于存储所有 n 个集合，以便后续遍历vector<vector<int>> sets(n); for(int i = 0; i < n; i++) { // 循环 n 次，读入 n 个集合int l;cin >> l;// 预留 l 个空间，或者使用 push_backsets[i].resize(l); for (int j = 0; j < l; j++) {int a;cin >> a;counts[a]++;      // 统计数字 a 出现的次数sets[i][j] = a; // 把数字 a 存入第 i 个集合}}// 2. 检查“全选”是否可行bool all_valid = true;for(int i = 1; i <= m; i++) {if (counts[i] == 0) {// 如果有数字一次都没出现过，方案数为 0all_valid = false;break;}}if (!all_valid) {cout << "NO" << endl;continue; // 直接处理下一个测试用例}// --- 能运行到这里，说明“全选”是第 1 种方案 ---// 3. 寻找“可移除的”集合int removable_count = 0;// 遍历 n 个集合 (i 是集合的索引)for(int i = 0; i < n; i++) {bool can_remove = true; // 假设第 i 个集合可以移除// 遍历第 i 个集合 (sets[i]) 中的所有元素 xfor(int x : sets[i]) {// 核心逻辑：如果 S_i 包含了一个“独苗”元素if (counts[x] == 1) {// 那么 S_i 就是不可移除的can_remove = false; break; // 不用再检查 S_i 的其他元素了}}// 如果检查完 S_i 的所有元素，can_remove 仍然是 trueif (can_remove) {removable_count++;}}// 4. 最终判断if (removable_count >= 2) {// 方案 1: All// 方案 2: All \ {S_i}// 方案 3: All \ {S_j}cout << "YES" << endl;} else {// removable_count = 0 (只有 "All" 1种方案)// removable_count = 1 (只有 "All" 和 "All \ S_k" 2种方案)cout << "NO" << endl;}}return 0;
}