P4411

ytb2024 · 2022-12-06 22:12:24 · 题解

题目传送门

题意：从头到尾选数，相邻两个数的 \gcd 应大于等于 L，最多能选多少个数。

30 pts

相信很多同学的第一想法是 DP。一维 f_i 表示选当前的这个数的最大值，可以 O\left(n^2\right) 实现。具体为（不会写公式的蒟蒻 qwq），j<i 且 \gcd\left(a_i,a_j\right)\ge L 时，f_i=f_j+1，f_i 取最大值。最后 ans 为所有 f_i 中的最大值。

下面是代码实现，就不加注释了。（看一看前面的就知道）

#include<bits/stdc++.h>
using namespace std;
int n,l,a[50001],f[50001],ans=1;
inline void init()
{
    cin>>n>>l;
    for(int i=1;i<=n;i++)cin>>a[i],f[i]=1;
}
inline void solve()
{
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<i;j++)if(__gcd(a[i],a[j])>=l)f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]);
    }
    cout<<ans;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    init(),solve();
    return 0;
}

100 pts

我们可以发现，题目中的 L 与 a_i 不超过 10^6。

而对 \gcd\left(a_i,a_j\right)\ge{L} 的理解可以转化成 a_i 与 a_j 的相同约数至少要为 L。

由于 L 与 a_i 很小，所以考虑预处理所有 a_i 的约数，但是小于 L 的可以不管(后面会提到)。

注意：由于此题空间很小，如果数组的第二维开得太大了，就会MLE。这里经过计算后，10^6 内约数最多（不包含 1）的是 720720，有约数 239 个，所以考虑第二维开 250。

for(int i=1;i<=n;i++)
{
    int x;
    cin>>x;
    for(int j=1;j*j<=x;j++)if(x%j==0)
    {
        if(j>=l)a[i][++t[i]]=j;
        if(x/j>=l&&j*j!=x)a[i][++t[i]]=x/j;
    }
}

可以发现这相当于一个一个的组，在同一个组的数是可以用前面的更新后面的，而小于 L 的明显是不可以更新值的，而上面的预处理便是把它的每一个组记录下来。

可以对每一个组开一个数组，表示这个组中目前的最大值。对于每个数，从它所在的所有组中选最大值，+1 后将它在的组全部更新为这个数。

for(int i=1;i<=n;i++)
{
    int sum=0;
    for(int j=1;j<=t[i];j++)sum=max(sum,maxn[a[i][j]]+1);
    ans=max(ans,sum);
    for(int j=1;j<=t[i];j++)maxn[a[i][j]]=sum;
}

最后输出 ans 就可以 AC 啦。

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,l,a[50001][250],t[50001],maxn[1000001],ans;
inline void init()
{
    cin>>n>>l;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        for(int j=1;j*j<=x;j++)if(x%j==0)
        {
            if(j>=l)a[i][++t[i]]=j;
            if(x/j>=l&&j*j!=x)a[i][++t[i]]=x/j;
        }
    }
}
inline void solve()
{
    for(int i=1;i<=n;i++)
    {
        int sum=0;
        for(int j=1;j<=t[i];j++)sum=max(sum,maxn[a[i][j]]+1);
        ans=max(ans,sum);
        for(int j=1;j<=t[i];j++)maxn[a[i][j]]=sum;
    }
    cout<<ans;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    init(),solve();
    return 0;
}