CF1463F Max Correct Set 做题记录

定义集合 $S$ 合法当且仅当满足以下条件：

• $S \subseteq \{1,2,...,n\}$；

• $\forall a\in S,b\in S$， $|a-b|\not\in\{x,y\}$；

给定 $n,x,y$，求最大的 $|S|$。

$1\le n\le 10^9$，$1\le x,y\le 22$。

问题等价于找到一个长 $n$ 的 01 序列满足序列中任意两个 $1$ 的位置差不为 $x$ 或 $y$，最大化 01 序列中 $1$ 的个数。

引理 1

任意长 $x+y$ 的合法的 01 序列无限重复构成的 01 序列仍然合法。

证明

反证法。

若存在一个长 $x+y$ 的合法的 01 序列 $s$ 满足其无限重复构成的 01 序列 $a$ 中：

• $a_i$ 和 $a_{i+x}$ 均为 $1$：不妨假设 $i\le x+y,i+x>x+y$，那么此时一定有 $a_{i+x-x-y}=a_{i-y}=1$，注意到 $a_i$ 为 $1$，$i-y\le x+y$，所以此时 $s$ 一定不合法；
• $a_i$ 和 $a_{i+y}$ 均为 $1$：同理，一定有 $a_i=a_{i-x}=1$；

Q.E.D.

定理 1

最优解一定是某个长 $x+y$ 的合法 01 序列无限重复构成的 01 序列的长度为 $n$ 的前缀。

证明

$n\equiv 0\pmod {x+y}$ 的情况下显然成立。

设 $n\equiv r\pmod{x+y}$（$r\not=0$），现在来证明最后一小段长 $r$ 的跟着前面循环是不劣的：

• 反证法，设最后一小段长 $r$ 的 01 序列为 $t$，设循环节（长度为 $x+y$ 的不断出现的 01 串）为 $s$；
• $t$ 不跟着前面循环更优，当且仅当 $st$（拼起来）合法但用 $t$ 替换掉 $s$ 的长 $|t|$ 的前缀不合法，不妨设用 $t$ 替换掉 $s$ 的长 $|t|$ 的前缀得到的字符串为 $ts'$；
• 设 $ts'$ 中不合法的两个位置为 $i$ 和 $i+x$（$i+y$ 同理），那么一定有 $i\le |t|,i+x>|t|$；
• 考察答案的后缀 $ts't$，由于位置 $i$ 和 $i+x$ 都是 $1$，那么位置 $i+x$ 和 $i+x+y$ 一定也都是 $1$，那么 $s't$ 不合法，所以 $st$ 不合法，矛盾；

Q.E.D.

那么 $O((x+y)2^{\max(x,y)})$ 状压 dp 即可，代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int BS=1<<22;

int n,x,y;
int f[2][BS];

int main()
{
	scanf("%d%d%d",&n,&x,&y);
	if(x<y) swap(x,y);
	memset(f,128,sizeof(f));
	int p=0;
	f[p][0]=0;
	for(int i=0;i<=x+y-1&&i<=n-1;i++)
	{
		p^=1;
		memset(f[p],128,sizeof(f[p]));
		for(int j=0;j<(1<<x);j++)
		{
			int s0=(j<<1)&((1<<x)-1),s1=s0|1;
			if((s0&(j>>x-1))==0&&(s0&(j>>y-1))==0) f[p][s0]=max(f[p][s0],f[p^1][j]);
			if((s1&(j>>x-1))==0&&(s1&(j>>y-1))==0) f[p][s1]=max(f[p][s1],f[p^1][j]+n/(x+y)+(i+1<=n%(x+y)));
		}
	}
	int ans=0;
	for(int i=0;i<(1<<x);i++) ans=max(ans,f[p][i]);
	printf("%d\n",ans);
	return 0;
}