CF1463F Max Correct Set(取小样法+状压 DP)

CF1463F Max Correct Set

要求选出集合 \(U=\{1,2,3,\dots,n\}\) 的一个子集 \(S\),满足:如果 \(a \in S\) 并且 \(b \in S\),那么 \(|a-b| \not ={x}\) 并且 \(|a-b| \not ={y}\)。求集合 \(S\) 大小的最大值。

\(1\le n\le 10^9,1\le x,y\le 22\)

考虑一个简化版本:如果只有一个限制 \(x\),要求集合中任意两个数之差不为 \(x\),求集合最大值。

那么可以将整个 \(1,\dots,n\) 序列分为 \(\frac{n}{2x}\) 段,隔一段全部选择,两边特判一下,求最大值。

这是不是很像 “取小样法” ?将所有数划分为一段又一段,那么每一段后面都是重复出现的。

什么是 “取小样法”

小学奥数常常有比如这样的题:我们称 \(x\equiv a\pmod{c},x\equiv b\pmod{d}\) 的正整数 \(x\) 为“完美数”,求 \(\le n\) 的“完美数”数量,\(n\le 10^9,1\le c,d\le 15\),手算。

这是我们可以取出 \([1,\gcd(c,d)]\) 这么一小段,计算这一段内有多少“完美数”,乘以段数,加上边界上的数量。这样就可以手动快速计算。

其中“小样”的本质是若干不互相影响具有代表性的子集,通过计算子集的答案可以反映整体答案。

但是这里并不是将 \(\gcd(x,y)\) 作为“小样”的长度,只用选择 \(x+y\) 作为“小样”的长度即可。

为什么可以用 \(x+y\) 作为“小样”?

设两个数 \(a,b(a<b)\) 不能够同时存在,那么他们一定有 \(a+x=b\)\(a+y=b\)或者说 \(b-a\equiv \pm x\pmod{x+y}\)

这个同余式说明如果长度为 \(x+y\) 的段内部合法,整个序列就可以用这个段重复多次表示出来且一定合法,满足了不互相影响的特点。

那么需要求出最优的一个“小样”使得答案最大,状压 DP 即可。

#define Maxsta 4194500
ll n,m,x,y,All,p,q,ans;
ll f[Maxsta],g[Maxsta];
int main()
{
	n=rd(),x=rd(),y=rd();
	m=x+y,All=1<<max(x,y);
	p=n/m,q=n%m;
	for(int i=1;i<=m;i++)
	{
		memcpy(g,f,sizeof(f)),memset(f,0,sizeof(f));
		for(int s=0,t;s<All;s++)
		{
			t=(s<<1)&(All-1);
			f[t]=max(f[t],g[s]);
			if(!((s>>(x-1))&1) && !((s>>(y-1))&1))
				f[t|1]=max(f[t|1],g[s]+p+(i<=q));
		}
	}
	for(int s=0;s<All;s++) ans=max(ans,f[s]);
	printf("%lld\n",ans);
	return 0;
}

原文地址:http://www.cnblogs.com/EricQian/p/16852411.html

发表评论

您的电子邮箱地址不会被公开。