N题K人，给出N行K列数据，aij为1代表i题被第j个人所了解。求是否能找出一套题（在这N题中找任意题）使得每个人了解的题不超过这套题数目的一半。(1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 4) 

需要先证明要么使用一道题，要么使用两道题，如果有解，那么答案有解，否则答案无解。（一道是特殊情况，当存在多道题构成的解，我们可以反证，说明其中必然有两道可以满足条件）

注意到k很小，我们就会联想到状压dp.

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define INF 0x3f3f3f3f 6 #define MOD 1000000007 7 using namespace std; 8 typedef long long LL; 9 10 int N, K;11 const int max_s = 20;12 bool vis[max_s];13 14 int main() {15     scanf("%d%d", &N, &K);16     for (int i = 1; i <= N; i++) {17         int state = 0;18         for (int j = 1; j <= K; j++) {19             int t;20             scanf("%d", &t);21             state |= ((1 << (j - 1)) * t);22         }23         vis[state] = 1;24     }25     bool flag = 0;26     for (int i = 0; i < (1 << 4) && !flag; i++) {27         for (int j = 0; j < (1 << 4) && !flag; j++) {28             if (!vis[i] || !vis[j]) continue;29             if ((i & j) == 0) {30                 flag = 1;31             }32         }33     }34     if (flag) {35         puts("YES");36     } else {37         puts("NO");38     }39     return 0;40 }