2020 CCPC Wannafly Winter Camp Day5 A

2020 CCPC Wannafly Winter Camp Day5 A
链接：https://ac.nowcoder.com/acm/contest/4120/A
来源：牛客网
Everybody knows that jiry_2 = Syloviaely. There are n{n}n different accounts on the website, and some of them competed in the recent k{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 integersn,k (1≤n≤105,1≤k≤3)n, k(1\leq n\leq 10^5, 1\leq k\leq 3)n,k (1≤n≤105,1≤k≤3).Each of the following k{k}k lines contains an integer m (1≤m≤n)m(1\leq m\leq n)m (1≤m≤n)first, followed by m{m}m distinct integers xi (1≤xi≤n)x_i~(1\leq x_i\leq n)xi​ (1≤xi​≤n) indicating the accounts participating the contest.Some accounts may not participate in any contests.
输出描述:
Output one integer - the answer.

示例1

输入
复制

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

输出
复制

4
每个账号情况：
1.三场都参加
2.参加两场 12/13/23
3.参加一场 1/2/3
4.一场都没参加

K==3
一场都没参加，不需要考虑
三场都参加确定一个人 ans+=cnt123
参加两场如： 12 和 3 对应，二者较小可确定其较小值必定参加 ans+=min(cnt12,cnt3)
13 和 2 --> ans+=min(cnt13,cnt2) ...ans+=min(cnt23,cnt1)
匹配后减去其最小值 cnt12-=min(cnt12,cnt3) cnt3-=min(cnt12,cnt3)
只参加一场 ans+=max(max(cnt1,cnt2),cnt3)
最后 ans+=cnt12+cnt13+cnt23

K==1,直接输出m
K==2，ans+=cnt12 ans+=max(cnt1,cnt2)

#pragma warning (disable :4996)
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
const int Max = 1e5 + 50;
int a[Max][6];
int n, k, m;
int q[4];
int main()
{
    scanf("%d %d", &n, &k);
    memset(a, 0, sizeof(a));
    int m;
    for (int i = 1; i <= k; i++) {
        scanf("%d", &q[i]);
        for (int j = 1; j <= q[i]; j++) {
            int num;
            scanf("%d", &num);
            a[num][i]++;
        }

    }
    int ans = 0;
    int cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt12 = 0, cnt13 = 0, cnt23 = 0, cnt123 = 0, cnt0 = 0;
    if (k == 1) {
        cout << q[1] << endl;
        return 0;
    }
    if (k == 2) {
        for (int i = 1; i <= n; i++) {
            if (!a[i][1] && !a[i][2])
                cnt0++;
            if (!a[i][1] && a[i][2])
                cnt2++;
            if (a[i][1] && !a[i][2])
                cnt1++;
            if (a[i][1] && a[i][2])
                cnt12++;
        }
        ans += cnt12;
        ans += max(cnt1, cnt2);
        cout << ans << endl;
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        if (!a[i][1] && !a[i][2] && !a[i][3])
            cnt0++;
        if (a[i][1] && !a[i][2] && !a[i][3])
            cnt1++;
        if (!a[i][1] && a[i][2] && !a[i][3])
            cnt2++;
        if (!a[i][1] && !a[i][2] && a[i][3])
            cnt3++;
        if (a[i][1] && a[i][2] && !a[i][3])
            cnt12++;
        if (a[i][1] && !a[i][2] && a[i][3])
            cnt13++;
        if (!a[i][1] && a[i][2] && a[i][3])
            cnt23++;
        if (a[i][1] && a[i][2] && a[i][3])
            cnt123++;
    }
    ans += cnt123;
    if (cnt12 >= cnt3)
    {
        ans += cnt3;
        cnt12 -= cnt3;
        cnt3 = 0;
    }
    else
    {
        ans += cnt12;
        cnt3 -= cnt12;
        cnt12 = 0;

    }

    if (cnt13 >= cnt2)
    {
        ans += cnt2;
        cnt13 -= cnt2;
        cnt2 = 0;
    }
    else
    {
        ans += cnt13;
        cnt2 -= cnt13;
        cnt13 = 0;

    }

    if (cnt23 >= cnt1)
    {
        ans += cnt1;
        cnt23 -= cnt1;
        cnt1 = 0;
    }
    else
    {
        ans += cnt23;
        cnt1 -= cnt23;
        cnt23 = 0;

    }
    ans += cnt12 + cnt13 + cnt23 + max(max(cnt1, cnt2), cnt3);

    cout << ans << endl;
    return 0;
}