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

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.

输入描述:

输出描述:

Output one integer - the answer.

输入

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

输出

4

题意

题解

AC-Code

#include 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。