【题解】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;
}