青岛建设网站设计公司百度旗下13个app

题意就是有n个集合，对n个集合做并集得到$S$, 现在抽n个集合中的集合做交集得到$T$，问如何做让$S\ne T$,并且让$T$尽可能大。

这道题如果数据大一些做不了，但是数字大小只在50之间，并且集合的大小50,n大小50。 我们可以用一个long long字符来存储集合的情况，因为$S\ne T$，所以我们可以枚举不在集合里的数字，然后排出有这个数字的集合。统计情况就行了。
复杂度就是n*50= 2500，非常快

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
void solve()
{int n;cin >> n;ll S = 0;vector<ll> s;for (int i = 1; i <= n; i++){int m;cin >> m;ll t = 0;for (int j = 1; j <= m; j++){ll x;cin >> x;S |= (1ll << x);t |= (1ll << x);}s.push_back(t);}int mx = 0;for (int i = 1; i <= 50; i++){ll X = 0;if ((S >> i & 1) == 1){ll t =  0;for (ll x : s){   if ((x >> i & 1) == 0){t |= x;}}X |= t;}mx = max(mx, __builtin_popcountll(X));}cout << mx << "\n";
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--){solve();}return 0;
}