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