题解 CF1463F【Max Correct Set】

· · 题解

将问题转为，求一个 01 序列，要求长度为 n，任意两个 1 的距离不是 x,y，最大化 1 的个数。

注意到只要一个长度为 x+y 的循环节合法，那把它一直重复并截取的任一区间都合法。

然后注意到最优解一定可以写成 x+y 循环节循环多次的形式，因为只要不是那把所有都替换成最大的那一段一定更优。

其实这东西证明并不简单……

证明方法：假设 n\ \mathrm{mod}\ (x+y)\ne 0，等于 0 是显然的。则把 1\sim n 分为若干个段，从左往右，第奇数个段（下表从 1 开始）的长度是余数 r，偶数段的长度是 x+y-r，共有奇数个段。设 dlt_i 表示把所有与第 i 个段的下标奇偶性相同的段全部改为 i，序列中 1 的个数的变化量（不考虑合不合法）。显然 \sum_{k} dlt_{2k+1}=\sum_k dlt_{2k}=\sum_k dlt_k=0。我们要证明的，其实是 \exists x,dlt_x+dlt_{x+1}\ge 0。反证，假设不存在，即 \forall x,dlt_x+dlt_{x+1}<0，则

  • 以此类推得到 \forall k,dlt_{2k+1}>0。

与 \sum_k dlt_{2k+1}=0 矛盾。

这样就可以设计 O(2^{\max(x,y)}(x+y)) 的状压 dp 了，但其实有 O(x+y) 的做法。

首先把 \gcd(x,y) 强制变为 1，即按照 \mathrm{mod}\ \gcd(x,y) 分组，只有两种本质不同的组，可以参照代码理解。

注意到一段里面不合法的数 a,b 满足 |a-b|=x 或 |a-b|=y，即 |a-b|\equiv \pm x\pmod {x+y}。由于 \gcd(x,y)=1，假如在任意 0\le p<x+y 的 p, (p+x)\ \mathrm{mod}\ (x+y) 之间连一条双向边，这个图一定是个大环。因此，不合法的数对等价于在环上相邻的数对。

至此问题转化为：在一个环上，求出最大权（p 的权即为 \sum_{i=1}^n [i\ \mathrm{mod}\ (x+y)=p]）独立集。简单 dp 即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,x,y,f[50][2][2],cnt[50];
int Solve(int n,int x,int y){
    int g=__gcd(x,y);
    if(g!=1)return (g-n%g)*Solve(n/g,x/g,y/g)+(n%g)*Solve(n/g+1,x/g,y/g);
    for(int i=0;i<x+y;i++)cnt[i]=(n-1)/(x+y)+((n-1)%(x+y)>=i);
    f[0][1][1]=cnt[0];
    for(int i=1,cur;i<x+y;i++){
        cur=x*i%(x+y);
        if(i!=x+y-1)f[i][1][1]=f[i-1][0][1]+cnt[cur];
        f[i][0][1]=max(f[i-1][1][1],f[i-1][0][1]);
        f[i][1][0]=f[i-1][0][0]+cnt[cur];
        f[i][0][0]=max(f[i-1][1][0],f[i-1][0][0]);
    }
    return max({f[x+y-1][0][0],f[x+y-1][0][1],f[x+y-1][1][0],f[x+y-1][1][1]});
}
int main(){
    cin>>n>>x>>y;
    cout<<Solve(n,x,y);
}