[atAGC106E]Medals

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

考虑Hall定理，即有完美匹配当且仅当$\forall S\subseteq V_{left}$，令$S'=\{x|\exists y\in 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 }

巴特西

[atAGC106E]Medals

最新文章

热门文章