正题

题目链接: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\leq n\leq 18,1\leq k,A_i\leq 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^nn\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定理,高维前缀和】

正题

题目大意

解题思路

code

最新文章

热门文章