8.14

CF1463F

题意：

规定一组正整数 \(S\)。当且仅当满足以下条件时该组正整数成立：

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

• 如果 \(a \in s\) 并且 \(b \in s\)，那么 \(|a - b| \not ={x}\) 并且 \(|a - b| \not ={y}\)

对于给定的数值 \(n,x,y\)，你需要找到成立数组的最大长度

\(1\leq n\leq 10^9,1\leq x,y\leq 22\)

题解：

把数组转化为\(1\sim n\)的\(01\)序列，问题就是不能有两个之间的距离是\(x\)或\(y\)，有最多有多少个\(1\)。

然后就是一种\(O(n*2^{max(x,y)})\)的状压做法

其实看\(n\)这么大也知道肯定要把这个\(n\)干掉。

结论就是这个序列以\(x+y\)为周期循环。

循环节之间是互不影响的。

为什么呢？假如不再一个循环节里的两个位置\(a,b\)，满足\(b-a=x\)，那么\(a-(b-x-y)=y\)，而且\(b-x-y\)和\(a\)在同一个循环节里。

这就说明如果相邻循环节之间的位置冲突，那这个循环节内部自己也冲突。

只要循环节里不冲突就行。

这样就可以\(O((x+y)*2^{max(x,y)})\)

根据大佬的说法，可以做到\(O(x+y)\)

一段区间里不合法的位置\(a,b\)满足\(|a-b|=±x(mod\ x+y)\)

对于任意位置\(0\leq p\leq x+y\)，向\(p+x\ mod\ (x+y)\)连边，那么图中会分出几个环。答案就是这几个环上的最大独立集。

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
    const int N=1e6+10,mod=1e9+7,inv2=5e8+4,inf=2e15;
    void __init(int n=2000) {}
    
    inline void main()
    {
        int n,x,y;cin>>n>>x>>y;
        int m=x+y;
        int S=(1<<22);
        vector dp(2,vector<int>(S,-inf));
        dp[0][0]=0;
        int ans=0,opt=0;
        for(int i=1;i<=m;++i)
        {
            opt^=1;
            for(int k=0;k<S;++k) dp[opt][k]=-inf;
            for(int k=0;k<S;++k)
            {
                dp[opt][(S-1)&(k<<1)]=max(dp[opt][(S-1)&(k<<1)],dp[opt^1][k]);
                if((k>>(x-1))&1) continue;
                if((k>>(y-1))&1) continue;
                dp[opt][((S-1)&(k<<1))|1]=max(dp[opt][((S-1)&(k<<1))|1],dp[opt^1][k]+n/m+(n%m>=i));
            }  
            for(int k=0;k<S;++k) ans=max(ans,dp[opt][k]);
        }
        cout<<ans<<'\n';
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    red::__init();
    int qwq=1; //cin>>qwq;
    while(qwq--) red::main();
    return 0;
}
/*

*/