B. Sets and Union

原创于 2023-09-27 17:49:06 发布 · 粉丝可见 · 2.2k 阅读 · 6 · 5 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/133358374

题目：

样例：

`cobol<br/>4<br/>3<br/>3 1 2 3<br/>2 4 5<br/>2 3 4<br/>4<br/>4 1 2 3 4<br/>3 2 5 6<br/>3 3 5 6<br/>3 4 5 6<br/>5<br/>1 1<br/>3 3 6 10<br/>1 9<br/>2 1 3<br/>3 5 8 9<br/>1<br/>2 4 28<br/>`

4 5 6 0

思路：

这里题目的意思是，要求合并尽可能多的集合，使它的集合大小最大，但是不能等于全部集合的合并。

这里由于题目所给的范围较小，所以我们可以暴力枚举，其次，里面也有贪心的成分，这里我们换个思路，我们通过总的集合，根据总的集合中的某个元素，枚举不存在该元素的集合，并合并，就是不等于全部集合的合并，取个合并后的集合个数 max，就是答案。

代码详解如下：

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define uset unordered_set
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;

inline void solve()
{	
	int t,ans = 0;
	
	umap<int,vector<int>>v;	// 记录每个集合
	
	uset<int>sum;	// 统计总集合
	
	cin >> t;	// t 为集合个数
	for(int i = 1;i <= t;++i)
	{
		int n;	// 集合大小
		cin >> n; 
		for(int j = 1;j <= n;++j)
		{
			int x;	// 集合元素
			cin >> x;
			
			// 记录该集合
			v[i].emplace_back(x);
			
			// 统计总集合元素
			sum.insert(x);
		}
	}
	
	// 开始 贪心删除
	for(auto now : sum)
	{	
		// 选择删除后的合并集合
		uset<int>tem;
		
		for(int i = 1;i <= t;++i)
		{
			// st 标记是否删除该集合
			bool st = false;
			
			// 遍历该集合
			for(auto j : v[i])
			{
				// 如果 sum 中的某个元素存在该集合
				// 那么我们选着的是删除这个集合
				// 所以无需添加
				if(now == j)
				{
					st = true;
					break;
				}
			}
			
			// 如果该集合不用删除，那么我们就添加该集合的元素
			if(!st)
			{
				for(auto j : v[i]) tem.insert(j);
			}	
		}
		// 判断选择删除这个元素后的，所有集合大小
		// 选择答案 合并集合个数最大，但不等于 sum 集合
		ans = max(ans,(int)tem.size());
	}
	
	cout << ans << endl;
}

int main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}