Educational Codeforces Round 115 (Rated for Div. 2)

B. Groups

思路:

只要找到是否有两天满足条件即可,我们可以这么分析,对于任意的两天,看这n组学生:

一天有课且另一天没课的记为cnt1

一天没课且另一天有课的记为cnt2

两天都有课的记为cnt3

两天都没课的记为cnt4

而两天都有课cnt3的可以放到cnt1中也可以放到cnt2中,我们只要满足cnt1+cnt3>=n/2,且cnt2+cnt3>=n/2,且cnt4==0,就代表有方案

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <vector>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int>PII;

const int N = 200010;
const int MOD = 1000000007;

int a[N][6];

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= 5; j++)
                cin >> a[i][j];

        bool flag = false;
        for (int i = 1; i <= 5; i++)
            for (int j = i + 1; j <= 5; j++)
            {
                int cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0;
                for (int k = 1; k <= n; k++)
                {
                    if (a[k][i] && !a[k][j]) cnt1++;
                    if (!a[k][i] && a[k][j]) cnt2++;
                    if (a[k][i] && a[k][j])  cnt3++;
                    if (!a[k][i] && !a[k][j]) cnt4++;
                }
                if (cnt1 + cnt3 >= n / 2 && cnt2 + cnt3 >= n / 2 && cnt4 == 0) flag = true;
            }

        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

 

上一篇:题解 a


下一篇:爬虫实战——爬取C语言100例