正题

题目链接:https://atcoder.jp/contests/arc106/tasks/arc106_e

---

题目大意

$n$个员工，第$i$个在$[1,A_i]$工作，$[A_i+1,2\times A_i]$休息，$[2\times A_i+1,3\times A_i]$工作…以此类推。

然后每天可以为一个在工作的人发一枚奖牌，至少多少天才能让每个人都有$k$块奖牌。

$1\le n\le 18,1\le k,A_i\le 10^5$

---

解题思路

首先答案上限显然是$2\times n\times 10^5$（就是每个人轮流发）

然后考虑一个暴力的做法。先二分，然后把每天看做一个右边的点，每个员工看做$k$个左边的点，然后一个员工干活的天就连边，之后暴力跑网络流。

这样显然会$T$但是这是一个正解的启示。

首先我们先拓宽一下$hall$定理，原来是$2\times k$个点的二分图匹配左边任意$k$个点都和右边至少$k$个点匹配是这张图有完全匹配的充要条件，但是不难发现如果右边多加了几个点显然还是满足条件的。

所以上面那个可以理解为左边任意$k$个点都和右边至少有$k$条连边，然后不难发现段其实只有$2^n$种不同的，所以我们直接二分一个答案然后设$f_s$表示包含集合$s$的段匹配了多少个点。

如果$f_s<|s|\times k$就无解了，然后$f_s$要用高维前缀和或者$FWT$做就好了。

时间复杂度$O(2^{n}n\log nk)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=18; ll n,k,a[N],bit[1<<N],f[1<<N],s[N*200000]; bool check(ll t){ll MS=(1<<n);memset(f,0,sizeof(f));for(ll i=1;i<=t;i++)f[MS-1]++,f[s[i]^(MS-1)]--;for(ll i=0;i<n;i++)for(ll j=0;j<MS;j++)if(j&(1<<i))f[j^(1<<i)]+=f[j];for(ll i=0;i<MS;i++)if(f[i]<bit[i]*k)return 0;return 1; } signed main() {scanf("%lld%lld",&n,&k);for(ll i=0;i<n;i++)scanf("%lld",&a[i]);ll MS=(1<<n),L=2*n*1e5;for(ll i=1;i<MS;i++)bit[i]=bit[i-(i&-i)]+1;for(ll i=1;i<=L;i++)for(ll j=0;j<n;j++)if((i-1)%(a[j]<<1)<a[j])s[i]|=(1<<j);ll l=1,r=L;while(l<=r){ll mid=(l+r)>>1;if(check(mid))r=mid-1;else l=mid+1;}printf("%lld\n",l);return 0; }

总结

以上是生活随笔为你收集整理的ARC106E-Medals【hall定理,高维前缀和】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。