2020 CCPC-Wannafly Winter Camp Day5 Div.1&2——A Alternative Accounts【状压】

​​题目传送门​​

---

题目描述

Everybody knows that jiry_2 = Syloviaely.
There are {n}n different accounts on the website, and some of them competed in the recent {k}k contests. However, Mike suspects that there are lots of alternative accounts.
There are axioms believed by everyone that nobody can use two different in one contest simultaneously and each account can be owned by only one person. So different accounts without overlapping contest participation can be owned by the same person.
Mike wants to know the minimum possible number of different people behind these accounts.

---

输入描述:

The first line contains two integers .
Each of the following lines contains an integer
first, followed by distinct integers
indicating the accounts participating the contest.
Some accounts may not participate in any contests.

---

输出描述:

Output one integer - the answer.

---

输入

5 3
2 1 2
3 2 3 4
4 4 5 1 2

---

输出

4

---

题意

• 给你个账号，有

---

题解

• 发现，就很简单了。考虑
• 对于三场都参加的账号，必定每个账号都是独立的一个人使用
• 稍加分析可以发现，如果人出现在了第场和第场，那么他还可能参加的其他账号，只能是只参加第
• 利用二进制状态压缩，对于每一个账户，记录这个账户参赛情况
• 记录不同参赛情况的人数
• 
  

---

AC-Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;

int state[maxn];
int num[8];//12(011)；13(101)；23(110)；123(111)
int main() {
int n, k;
while (cin >> n >> k) {
for (int i = 0; i < k; ++i) {
int t;
cin >> t;
for (int j = 0; j < t; ++j) {
int temp;
cin >> temp;
state[temp] |= (1 << i);
}
}
for (int i = 1; i <= n; ++i) ++num[state[i]];
int ans = num[7]; // 参加三天的账号数
for (int i = 0; i < 3; ++i) {
int x = 7 ^ (1 << i);// 参加两天
ans += num[x]; // 加上参加两天的人数
if (num[x] <= num[1 << i]) // 一天往两天合并（反之也可）
num[1 << i] -= num[x];
else
num[1 << i] = 0;
}
ans += max(num[1], max(num[2], num[4])); // 最后加上未被合并的最大账号数
cout << ans << endl;
}
return 0;
}