[atAGC106E]Medals

暴力二分答案+网络流，点数为$onk)$，无法通过

考虑Hall定理，即有完美匹配当且仅当$forall Ssubseteq V_{left}$，令$S’={x|exists yin V_{left}且x,y)in E}$，满足$|S|le |S’|$

代入本题中，即$o2^{n})$枚举工人，判断前$i$天内这些工人中有人存在的天数>=工人数的$k$倍

（虽然每一个工人被裂为了$k$个点，但由于中$k$个点的出边相同，选多个不会增大$|S’|$，必然全选）

考虑如何统计，先预处理出每一天存在的工人的二进制，再将所有于其有交的二进制全部加1即可

反过来，就是所有与其无交点的二进制，即全部属于其补集的二进制，高位前缀和即可

还有二分上限的问题，可以证明是$2kn$的，这样可以保证每一个工人都出现了至少$kn$次，任取$k$次即可

考虑时间复杂度，总复杂度为$on^{2}k+n2^{n}+nk)log_{2}nk)$，可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 3600005
 4 int n,m,x,day[N],tot[N],f[N];
 5 bool pdint k){
 6     forint i=0;i<1<<n);i++)f[i]=0;
 7     forint i=1;i<=k;i++)f[day[i]]++;
 8     forint i=0;i<n;i++)
 9         forint j=0;j<1<<n);j++)
10             if j&1<<i))f[j]+=f[j^1<<i)];
11     forint i=0;i<1<<n);i++)
12         if tot[i]*m>k-f[1<<n)-1-i])return 0;
13     return 1;
14 }
15 int main){
16     scanf"%d%d",&n,&m);
17     forint i=0;i<n;i++){
18         scanf"%d",&x);
19         forint j=1;j<N-4;j++)
20             if j-1)/x%2==0)day[j]|=1<<i);
21     }
22     forint i=0;i<1<<n);i++)tot[i]=tot[i>>1]+i&1);
23     int l=1,r=N-5;
24     while l<r){
25         int mid=l+r>>1);
26         if pdmid))r=mid;
27         else l=mid+1;
28     }
29     printf"%d",l);
30 }

View Code