[图论记录]ARC106E Medals
command_block
2021-10-26 10:51:37
**题意** ： 你经营一家雇用 $n$ 名员工的商店。每个员工都有固定的工作周期。
具体地，从今天开始，第 $i$ 位员工重复以下内容：干 $A_i$ 天活，休息 $A_i$ 天。
从今天开始的每一天，你可以选择的当天上班的员工之一，颁发一枚奖章。（如果没有员工上班，那天你什么也不做。）
给每位员工颁发至少 $k$ 枚奖牌至少需要多少天？
$n\leq 18,k,A\leq 10^5$ ，时限$\texttt{3s}$。
------------
毛估估一下答案上界大概是 $nk$ 级别的，开个 $6nk$ 感觉非常稳。
建模：一个二分图，左部是员工，共 $n$ 个点；右部是日子，有无穷多个。若某个员工在某个日子上班，则连边。
问题相当于求至少保留多少个日子，才能使得二分图有完美匹配。
考虑二分，并使用（多重扩展） Hall 定理。
只需算出每个左部点（员工）集合的邻域大小 $H_S$。
记 $E_i$ 为第 $i$ 天的边集，则 $H_S=\sum\limits_{i}[E_i\cap S\neq \varnothing]=\sum\limits_{i}1-[\neg E_i\supseteq S]$。
可以高维后缀和（超集和）计算。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 100500
#define MaxS 270000
using namespace std;
const int INF=1000000000;
int n,k,cnt[MaxS],o[MaxS],s[11000000];
bool chk(int lim)
{
for (int i=0;i<(1<<n);i++)o[i]=0;
for (int t=0;t<lim;t++)o[s[t]]++;
for (int len=1;len<(1<<n);len<<=1)
for (int p=0;p<(1<<n);p+=len+len)
for (int k=0;k<len;k++)
o[p|k]+=o[p|k|len];
for (int i=1;i<(1<<n);i++)
if (cnt[i]*k>lim-o[i])return 0;
return 1;
}
int a[20];
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<(1<<n);i++)
cnt[i]=cnt[i>>1]+(i&1);
for (int i=0,a;i<n;i++){
scanf("%d",&a);
for (int j=0;j<6*n*k;j+=a+a)
for (int t=j+a;t<j+a+a;t++)
s[t]|=(1<<i);
}
int l=0,r=6*n*k,mid;
while(l<r){
mid=(l+r)>>1;
if (chk(mid))r=mid;
else l=mid+1;
}printf("%d",r);
return 0;
}
```