题目描述
想象学竞赛网站 CodeFancy 举办了 \(m\) 场比赛。你在 CodeFancy 上关注了 \(n\) 个账号，编号为 \(1\) 到 \(n\)。你知道这 \(n\) 个账号分别参加了 \(m\) 场比赛中的哪些。但是你发现可能存在一个人使用多个账号的情况，你想知道这 \(n\) 个账号的使用者最少共有多少人。
具体地，账号和使用者的关系由两条规则限定：
- 一个人在一场比赛中至多使用一个账号。
- 一个账号的使用者只有恰好一个人。
输入格式
第一行两个正整数 \(n\) 和 \(m\)。
接下来 \(m\) 行，每行先输入一个正整数 \(k\)，表示参加这场比赛的账号数量；接下来输入 \(k\) 个正整数，表示参加这场比赛的账号编号。
输出格式
一行一个非负整数，表示最少的人数。
样例
输入样例
5 3
2 1 2
3 2 3 4
4 4 5 1 2
输出样例
4
样例解释
一种合法的方案是，四个人使用的账号集合分别为：{1,3},{2},{4},{5}。
可以证明，不存在人数更少的合法方案。
数据范围
本题使用捆绑测试，子任务信息如下：
| 子任务编号 | \(m\) | 分值 |
|---|---|---|
| 1 | 1 | 10 |
| 2 | 2 | 20 |
| 3 | 3 | 30 |
| 4 | 4 | 40 |
对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^5\)，\(1 \leq m \leq 4\)，\(1 \leq k \leq n\)。
-
解题思路：
题目背景
在一个编程竞赛平台上，有许多用户参加了多场比赛。每个用户可能拥有一个或多个账号，但规则是一个用户在同一场比赛中只能使用一个账号。给定每场比赛中参与的账号，目标是找出最少需要多少个独立的用户。
-
解题思路
步骤1: 编码参赛情况
首先，我们将每个账号的参赛情况编码为一个0到16之间的整数。这是通过将每场比赛视为一个位，如果账号参加了该比赛，则该位为1；否则为0。这样，每个账号都可以用一个整数表示其参赛情况。
步骤2: 计数相同参赛情况的账号
-
接下来，我们计算具有相同参赛情况的账号数量。这是通过使用一个数组
a[]完成的，其中a[i]存储具有相同编码 i 的账号数量。步骤3: 贪心凑合
-
然后，我们使用贪心策略尝试用最少的用户数覆盖所有账号。我们首先处理那些参加了最多比赛的账号，因为它们可以覆盖更多的比赛。具体操作如下：
-
处理全覆盖账号: 如果有账号参加了所有比赛（即编码为 15），我们首先选择这些账号，因为它们单独就覆盖了所有比赛。
-
配对互补集合: 对于剩下的账号，我们尝试找到互补的账号集合来覆盖所有比赛。例如，如果一个账号的编码是 12，我们会寻找编码为 3 的账号，因为这两个账号合起来可以覆盖所有比赛。
-
处理剩余账号: 对于不能与其他账号形成全覆盖配对的账号，我们尝试将它们分配给新的用户，同时确保这些新用户尽可能多地参加比赛。
步骤4: 输出结果
- 最后，我们得到了覆盖所有账号所需的最少用户数。 ### 根据输入：
5 3 2 1 2
3 2 3 4
4 4 5 1 2 -
账号的参赛情况如下：
- 账号 1: 参加了比赛 1 和 3。 - 账号 2: 参加了比赛 1、2 和 3（所有比赛）。 - 账号 3: 只参加了比赛 2。 - 账号 4: 参加了比赛 2 和 3。 - 账号 5: 只参加了比赛 3。-
按照你的策略，我们首先选择参加比赛最多的账号。在这里，账号 2 参加了所有比赛，所以我们首先选择它。由于账号 2 已经参加了所有的比赛，我们需要考虑其它的账号。在这种情况下，由于账号 2
已经覆盖了所有比赛，我们不需要选择其它账号，因为它们至少参加了账号 2
已经参加的比赛。然而，由于规则规定一个人在一场比赛中只能使用一个账号，所以参加同一场比赛的其它账号不能由账号 2 的用户使用。
因此，我们需要为参加了同一场比赛的其它账号分配不同的用户。在这个例子中： -
账号 1 可以由一个新用户使用，因为它与账号 2 参加了相同的比赛。
-
账号 3 也需要一个新用户，因为它与账号 2 和账号 4 参加了比赛 2。
-
账号 4 可以由账号 3 的用户使用，或者需要一个新用户（如果账号 3 的用户不使用它）。
-
账号 5 需要一个新用户，因为它与账号 2 和账号 4 参加了比赛 3。
综上所述，最少需要的用户数是 4：一个用户使用账号 2，三个新用户分别使用账号 1、3 和 5。这样，每个用户都遵守了规则，而且账号 2 的用户参加了最多的比赛。
这个策略确保了我们以最有效的方式使用了每个账号，同时遵守了比赛的规则。
-
-
AC代码
#include <bits/stdc++.h>
using namespace std;
// 定义一些宏来简化代码
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
const int N = 1e5 + 10;
// 定义函数读取输入数据
int read() {
int x = 0, f = 1;
char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
return x * f;
}
// 定义函数计算一个数的二进制表示中1的个数
int pc(int s) {
return __builtin_popcount(s);
}
int n, k, ans, a[N], cnt[16];
int main() {
// 读取账号数和比赛数
n = read(), k = read(), ans = n;
// 读取每场比赛的参与账号，并更新它们的参赛情况
rep(i, 0, k - 1) {
for (int c = read(), p; c; --c) {
p = read();
a[p] |= 1 << i; // 使用位运算记录账号 p 参加了哪些比赛
}
}
// 计算每种参赛情况的账号数
rep(i, 1, n) ++cnt[a[i]];
ans = 0; // 重置答案为0，准备通过计算得出
// 定义一个 lambda 函数来更新答案
auto upd = [&](int s) {
// 找到参赛情况互补的账号集合，并更新答案
int t = min(cnt[s], cnt[15 ^ s]);
ans += t;
cnt[s] -= t;
cnt[15 ^ s] -= t;
};
// 对于参加了多于一场比赛的账号，尝试找到互补集合
rep(s, 0, 15) if (pc(s) > 1) upd(s);
// 对于参加了多于两场比赛的账号，直接将它们计入答案
rep(s, 0, 15) if (pc(s) > 2) ans += cnt[s];
// 对于只参加了一场或两场比赛的账号，尝试配对它们
rep(i, 0, 3) rep(j, i + 1, 3) {
int t = min(cnt[15 ^ (1 << i) ^ (1 << j)], min(cnt[1 << i], cnt[1 << j]));
ans += t;
cnt[15 ^ (1 << i) ^ (1 << j)] -= t;
cnt[1 << i] -= t;
cnt[1 << j] -= t;
}
// 对于剩下的账号，尝试将它们分配给新的用户
rep(k, 0, 3) rep(i, 0, 3) rep(j, i + 1, 3) {
if (k == i || k == j || !cnt[(1 << i) | (1 << j)]) continue;
int t = min(cnt[(1 << i) | (1 << j)], cnt[1 << k]);
ans += t;
cnt[(1 << i) | (1 << j)] -= t;
cnt[1 << k] -= t;
}
// 最后，处理只参加了两场比赛的账号，并找出只参加了一场比赛的账号中数量最多的
rep(s, 0, 15) if (pc(s) == 2) ans += cnt[s];
ans += max(max(cnt[1], cnt[2]), max(cnt[4], cnt[8]));
// 输出答案，如果答案小于1（即没有账号参加比赛），则输出1
printf("%d\n", max(ans, 1));
return 0;
}