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

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性