题目大意

就是给你n个题目，有k个人参加考试
n≤$10^5$
k≤4
然后告诉你这k个人会什么题目
问你是否有一种出题方式使得每个人会的题目不超过一半

题解

这题想了很久都没有弄出来QAQ
只想到有一个有一个转化，就是说01状态一样的题是一样的。。
这样的话，最多就只有$2^k$也就是16种状态
然后。。然后。。就不会了
于是今早听说标解时如果可以在这16种状态里面，找到两个有且与起来为0的话，那么就是YES，否则就是NO
具体证明自己弄，我也没有TAT
话说我写了一个玄学的dfs只过了40个点。。真是菜啊
AC CODE：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int n,k;
int a[20];//这种状态有多少个 
int mx=0;
int shen[5];//这个人被选了多少此 
bool tf=false;
int p[20][5];
int ooo[20];
int tot=0;
void dfs (int x,int y,int y1,int z)//当前处理到的位置 最大是什么 那个数是什么 选了多少个数 
{if (tf) return ;if (y<=z/2&&z!=0)   {tf=true;return ;}if (x<1)    return ;if (y>((z+ooo[x]-p[x][y1])>>1)) return ;tot++;if (tot>=4000) return ;dfs(x-1,y,y1,z);for (int u=1;u<=a[x];u++)//选多少个{for (int i=1;i<=4;i++)//对于四个数 if (x&(1<<i-1)) shen[i]+=u;int kk=-1,lalal;for (int i=1;i<=4;i++)if (shen[i]>kk){kk=shen[i];lalal=i;}dfs(x-1,kk,lalal,z+u);if (tf) return ;if (tot>=4000) return ;for (int i=1;i<=4;i++)//对于四个数 if (x&(1<<i-1)) shen[i]-=u;}
}
int main()
{scanf("%d%d",&n,&k);mx=-1;for (int u=1;u<=n;u++){int x=0;for (int u=1;u<=k;u++){int lalal;scanf("%d",&lalal);x=(x<<1)+lalal;}mx=max(mx,x);a[x]++;}if (a[0]!=0) {
   printf("YES\n");return 0;}for (int u=1;u<mx;u++) ooo[u]=ooo[u-1]+a[u];for (int u=1;u<mx;u++){for (int i=1;i<=4;i++){if (u!=0) p[u][i]=p[u-1][i];if (u&(1<<i-1)) p[u][i]+=a[u];}}dfs(mx-1,0,1,0);if (tf) printf("YES\n");else printf("NO\n");return 0;
}