CF1463F Max Correct Set 做题记录

定义集合 SS 合法当且仅当满足以下条件:

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

  • aS,bS\forall a\in S,b\in Sab{x,y}|a-b|\not\in\{x,y\}

给定 n,x,yn,x,y,求最大的 S|S|

1n1091\le n\le 10^91x,y221\le x,y\le 22

问题等价于找到一个长 nn 的 01 序列满足序列中任意两个 11 的位置差不为 xxyy,最大化 01 序列中 11 的个数。

引理 1

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

证明

反证法。

若存在一个长 x+yx+y 的合法的 01 序列 ss 满足其无限重复构成的 01 序列 aa 中:

  • aia_iai+xa_{i+x} 均为 11:不妨假设 ix+y,i+x>x+yi\le x+y,i+x>x+y,那么此时一定有 ai+xxy=aiy=1a_{i+x-x-y}=a_{i-y}=1,注意到 aia_i11iyx+yi-y\le x+y,所以此时 ss 一定不合法;
  • aia_iai+ya_{i+y} 均为 11:同理,一定有 ai=aix=1a_i=a_{i-x}=1

Q.E.D.

定理 1

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

证明

n0(modx+y)n\equiv 0\pmod {x+y} 的情况下显然成立。

nr(modx+y)n\equiv r\pmod{x+y}r=0r\not=0),现在来证明最后一小段长 rr 的跟着前面循环是不劣的:

  • 反证法,设最后一小段长 rr 的 01 序列为 tt,设循环节(长度为 x+yx+y 的不断出现的 01 串)为 ss
  • tt 不跟着前面循环更优,当且仅当 stst(拼起来)合法但用 tt 替换掉 ss 的长 t|t| 的前缀不合法,不妨设用 tt 替换掉 ss 的长 t|t| 的前缀得到的字符串为 tsts'
  • tsts' 中不合法的两个位置为 iii+xi+xi+yi+y 同理),那么一定有 it,i+x>ti\le |t|,i+x>|t|
  • 考察答案的后缀 tstts't,由于位置 iii+xi+x 都是 11,那么位置 i+xi+xi+x+yi+x+y 一定也都是 11,那么 sts't 不合法,所以 stst 不合法,矛盾;

Q.E.D.

那么 O((x+y)2max(x,y))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;
}