【题解】CF1463F Max Correct Set

*3100 的思维题果然可怕。

我们用长度为 \(n\) 的序列 \(a\) 表示选择的集合。如果集合中包含数 \(i\) ,那么 \(a_i=1\) ,否则 \(a_i=0\)

那么我们需要找出包含 \(1\) 最多的长度为 \(n\)\(0/1\) 序列,使得任意两个 \(1\) 的间隔 \(\neq x\land \neq y\)

这就是经典问题,我们记录最后 \(\max\{x,y\}\) 个数的状态跑状压 \(\rm DP\) 可以做到 \(\mathcal{O}(n2^m)\)

从特殊到一般,我们可以先考虑 \(x=y\) 的情况。

\(x\mid n\) 时,我们可以将序列 \(a\) 分成 \(\frac{n}{x}\) 个长度为 \(n\) 的块,奇数块为 \(1\) ,偶数块为 \(0\),不难反证得这是最优解。

\(x\nmid n\) 时,按上述方法划分,最终会剩下 \(n\bmod x\) 个位置,显然这些位置要么全部都能填 \(1\) ,要么全部都能填 \(0\) ,判断一下即可。

一般化,我们构造的这个解是以长度 \(2x\) 的块为循环节,一直重复得到的方案。

所以我们猜测,对于 \(x\neq y\) ,也一定存在一个最优解是以循环长度为 \(x+y\) 的块一直重复得到的方案。

首先我们直到所有循环长度为 \(x+y\) 的方案,如果块内是合法的,则整个序列是合法的。反证如果不合法,即存在两个不在同一块的位置 \(a,b\ (a<b)\) 距离为 \(x\) ,而 \(a,b-x-y\) 距离为 \(y\) ,它们两个又在同一块内,所以结论得证。

再简要证明一下充分性。如果我们固定初始的 \(x+y\) 个位置,有 $k $ 个 \(1\),那么第 \(2\) 块中的 \(1\) 的个数 \(>k\) ,那么我们可以以第二块作为循环节得到更优的答案。否则一直重复第一个块一定最优。

状压 \(\rm DP\) 求出最优的循环节即可。时间复杂度 \(\mathcal{O}(m2^m)\)

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
int n,x,y,m,t,f[2][1<<22],ans;
inline void cmax(int &x,int y){if(y>x)x=y;}
int main(){
	scanf("%d%d%d",&n,&x,&y);
	m = x + y , t = 1 << 22;
	memset(f[0],0xcf,sizeof(f[0]));
	f[0][0] = 0;
	rep(i,1,m){
		int op = i & 1;
		memset(f[op],0xcf,sizeof(f[op]));
		rep(j,0,t-1){
			cmax(f[op][(t-1)&(j<<1)],f[op^1][j]);
			if(1 & (j >> (x - 1)))continue;
			if(1 & (j >> (y - 1)))continue;
			cmax(f[op][1^((t-1)&(j<<1))],f[op^1][j]+n/m+(n%m>=i));
		}
		rep(j,0,t-1)cmax(ans,f[op][j]);
	}
	printf("%d\n",ans);
	return 0;
}

【题解】CF1463F Max Correct Set

上一篇:使用Element UI报错


下一篇:ES系列(七):多节点任务的分发与收集实现