Qualification Rounds（Codeforces Round #438 by Sberbank and Barcelona Bootcamp (Div. 1 + Div. 2 combined)＋状态压缩）

时间：2025-01-05 21:37:44

题目链接

传送门

题意

现总共有\(n\)个题目\(k\)支参赛队伍，已知每个题目各队伍是否会写，现问你能否从题目中选出一个子序列使得每支队伍最多只会写一半的题目。

思路

对于每个题目我们用二进制压缩所有队伍的情况，然后通过枚举状态看是否存在两种完全不同的状态是否同时出现过。

代码实现如下

#include <set>

#include <map>

#include <deque>

#include <queue>

#include <stack>

#include <cmath>

#include <ctime>

#include <bitset>

#include <cstdio>

#include <string>

#include <vector>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef pair<LL, LL> pLL;

typedef pair<LL, int> pLi;

typedef pair<int, LL> piL;;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define lson rt<<1

#define rson rt<<1|1

#define lowbit(x) x&(-x)

#define name2str(name) (#name)

#define bug printf("*********\n")

#define debug(x) cout<<#x"=["<<x<<"]" <<endl

#define FIN freopen("in","r",stdin)

#define IO ios::sync_with_stdio(false),cin.tie(0)

const double eps = 1e-8;

const int mod = 1e9 + 7;

const int maxn = 1e5 + 7;

const double pi = acos(-1);

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3fLL;

int n, k;

int vis[25];

int main() {

    scanf("%d%d", &n, &k);

    for(int i = 1; i <= n; ++i) {

        int x, num = 0;

        for(int j = 0; j < k; ++j) {

            scanf("%d", &x);

            num <<= 1;

            num += x;

        }

        vis[num] = 1;

    }

    for(int i = 0; i < 16; ++i) {

        for(int j = 0; j < 16; ++j) {

            if(vis[i] && vis[j] && (i & j) == 0) {

                return puts("YES") * 0;

            }

        }

    }

    puts("NO");

    return 0;

}

相关文章