题目:
样例:
|
4 5 6 0 |
思路:
这里题目的意思是,要求合并尽可能多的集合,使它的集合大小最大,但是不能等于全部集合的合并。文章来源:https://www.toymoban.com/news/detail-728853.html
这里由于题目所给的范围较小,所以我们可以暴力枚举,其次,里面也有贪心的成分,这里我们换个思路,我们通过总的集合,根据总的集合中的某个元素,枚举不存在该元素的集合,并合并,就是不等于全部集合的合并,取个合并后的集合个数 max,就是答案。文章来源地址https://www.toymoban.com/news/detail-728853.html
代码详解如下:
#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;
}
最后提交:
到了这里,关于B. Sets and Union的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!