2 条题解
-
1
令sum为所有子集合的并集。
我们要找的集合S，必须满足是sum的子集，并且sum != S,在此基础上让S集合元素个数最大。
数据都在[1,50]，是一个突破点，说明我们可以枚举[1,50]中的每个数i ，让S合并所有不含i的子集a[] ，最后看看S元素个数和sum是否相同，不同的话，ans就更新最大值即可。
如何去实现，我们可以考虑2进制，因为数据都在[1,50], (2^50 不超过Long Long int 范围)
-
morgen
@ 2025-11-26 17:42:35
#define rep(i, l, r) for (int i = l; i <= r; i++) #define int long long void solve() { int n; cin >> n; vector<int> a(55); for(int i = 1; i <= n; i++){ int m;cin >> m; rep(j,1,m){ int x; cin >> x; a[i] |= (1LL << x); } } int sum = 0; rep(i,1,n) sum |= a[i]; int ans = 0; for(int i = 1; i <= 50; i++){ int S = 0; for(int j = 1; j <= n; j++){ if (a[j] & (1LL << i)) continue; S |= a[j]; } if(S == sum) continue; int cnt = 0; while(S){ cnt += S % 2; S /= 2; } ans = max(ans, cnt); } cout << ans << endl; } -
morgen
@ 2025-11-26 17:49:31
（1）：运用位运算 | , << 将值存到子集合a[]中
（2）：找到所有集合的并集sum
（3）：运用位运算 &, << 合并所有不出现i这个数的子集合，然后判断集合S是否合法.
（4）：运行2进制模拟，求出集合S的元素个数，然后取最大ans即可
-
- 1