Codeforces Round 899 (Div. 2) B. Sets and Union （模拟，数学）

你有 $n$ 个整数集合 $S_1,S_2,\dots ,S_n$ 。如果可以从 $S_1,S_2,\dots ,S_n$ 中选择一些(也可能一个都不选)，从而使 $S$ 等于它们的合集 ${}^{†}$ ，那么我们就把这个集合 $S$ 称为可达到的集合。如果在 $S_1,S_2,\dots ,S_n$ 中一个也不选，那么它们的联合就是空集。

求一个可达到的 $S$ 中元素的最大数目，使得 $S\ne S_1\cup S_2\cup \dots \cup S_n$ .

${}^{†}$ 集合$A_1,A_2,\dots ,A_k$ 的联集定义为至少存在于其中一个集合中的元素的集合。用 $A_1\cup A_2\cup \dots \cup A_k$ 表示。例如， $$\begin{gathered} 2,4,6 \\ \cup 2,3 \\ \cup 3,6,7 \\ =2,3,4,6,7 \end{gathered}$$ 。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1\le t\le 100$ )。测试用例说明如下。

每个测试用例的第一行都包含一个整数 $n$ ( $1\le n\le 50$ )。

接下来的 $n$行描述了集合 $S_1,S_2,\dots ,S_n$ 。其中第 $i$ 行包含一个整数 $k_i$ ( $1\le k_i\le 50$ ) - $S_i$ 中的元素个数，接下来是 $k_i$ 个整数 $s_{i,1},s_{i,2},\dots ,si,k_i$ ( $1\le s_{i,1}{s}_{i,2}\dots s_{i,k_i}\le 50$ ) - $S_i$ 中的元素个数。

输出

针对每个测试用例，打印一个整数 : $S$ 中可达到的最大元素个数，即 $S\ne S_1\cup S_2\cup \dots \cup S_n$ .

---

题意简化一下就是：找到给出的集合，找出他们中的某个并集，使得这个并集的长度是小于所有集合的并集的长度的条件下是长度最大的一个并集。

假设最大的并集长度就是 $len$，那么不能等于这个并集长度的最长的并集长度就是 $len-1$，也就是说我们就只需要找一个长度为 $len-1$ 的并集（如果存在的话），这个并集就满足了是最优解。

那么怎么找这样一个并集？如果一个集合中包含了一些数，那么只需要减少其中一个数，就可以得到一个长度减 $1$ 的并集，根据给出的数据范围，我们只需要循环 $1$ 到 $50$ 这些数，然后再去枚举集合，如果某个集合中不含有这个数就合并上这个集合，并维护一个最终并集的长度的最大值。

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;cin >> n;
        set<int>a[n];
        set<int>S;
        for(int i = 0;i < n;i++){
            int k;cin >> k;
            for(int j = 0;j < k;j++){
                int b;cin >> b;
                a[i].insert(b);
                S.insert(b);
            }    
        }
        int res = 0;
        int len = S.size();
        for(int i = 1;i <= 50;i++){
            S.clear();
            for(int j = 0;j < n;j++){
                if(a[j].count(i) == 0)
                    S.insert(a[j].begin(),a[j].end());
            }
            if(res < S.size() && S.size() < len){
                res = S.size();
            }
        }
        cout << res << endl;
    }
    return 0;
}

原文地址：https://blog.csdn.net/2302_79440616/article/details/137777710

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！