[atAGC106E]Medals

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

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

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

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

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

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

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

考虑时间复杂度，总复杂度为$o(n^{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 pd(int k){
 6     for(int i=0;i<(1<<n);i++)f[i]=0;
 7     for(int i=1;i<=k;i++)f[day[i]]++;
 8     for(int i=0;i<n;i++)
 9         for(int j=0;j<(1<<n);j++)
10             if (j&(1<<i))f[j]+=f[j^(1<<i)];
11     for(int 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     for(int i=0;i<n;i++){
18         scanf("%d",&x);
19         for(int j=1;j<N-4;j++)
20             if ((j-1)/x%2==0)day[j]|=(1<<i);
21     }
22     for(int 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 (pd(mid))r=mid;
27         else l=mid+1;
28     }
29     printf("%d",l);
30 }

View Code