题目描述

给出一个序列$ a_1  \dots   a_n$。

定义一个区间 \([l,r]\) 是好的，当且仅当这个区间中存在一个 \(i\)，使得 \(a_i\) 恰好等于 \(a_l, a_{l+1} \ \ \dots \ \ a_{r-1}, a_r\) 的最大公因数。

求最长的好的区间的长度。

输入描述:

第一行 n，表示序列的长度；第二行 n 个数 a1,a2,...,an。

输出描述:

输出一行一个数，表示最长的好的区间的长度。

乱搞就行，考试的时候睡了一觉就想出来了

用\(f[i]\) 表示前面第一个能被\(a[i]\)整除的位置

用\(g[i]\) 表示后面第一个能被\(a[i]\)整除的位置

则可以递推

f[1]=1;for(int i=2;i<=n;++i){    if(a[i]%a[f[i-1]]==0)f[i]=f[i-1];    else f[i]=i;}g[n]=n;for(int i=n-1;i;--i){    if(a[i]%a[g[i+1]]==0)g[i]=g[i+1];    else g[i]=i;}

最后在\(f\)和\(g\)里面连续的一段取最长的就行了

但是如果有这种数据:

510 6 6 6 9

我们写出\(f\)和\(g\)：

f: 1 2 2 2 5g: 1 4 4 4 5

发现有重复数字时位置会不一样

所以再用两个数组\(l[i]\)和\(r[i]\)乱搞一下

for(int i=1;i<=n;++i)    r[f[i]]=max(r[f[i]],i),    l[g[i]]=min(l[g[i]],i);for(int i=1;i<=n;++i)    r[i]=max(r[i],r[f[i]]),    l[i]=min(l[i],l[g[i]]);for(int i=1;i<=n;++i)ans=max(ans,r[i]-l[i]+1);

注意卡读入，用fread或者ios和tie优化都行

然后就没有然后了

可能我的思路比较别致

#include
    
     using namespace std;const int maxn = 4e6+5;#define int long long char getc(){    static char buf[maxn],*p1=buf,*p2=buf;    return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,maxn,stdin),p1==p2)? EOF:*p1++;}int mian(){    int s=0,f=1;char ch;    while(!isdigit(ch=getc()))(ch=='-')&&(f=-1);    for(s=ch-'0';isdigit(ch=getc());s=s*10+ch-'0');    return s*f;}int a[maxn],n,f[maxn],g[maxn],ans,l[maxn],r[maxn];signed main(){    n=mian();    for(int i=1;i<=n;++i)a[i]=mian(),l[i]=r[i]=i;    f[1]=1;    for(int i=2;i<=n;++i){        if(a[i]%a[f[i-1]]==0)f[i]=f[i-1];        else f[i]=i;    }    g[n]=n;    for(int i=n-1;i;--i)        if(a[i]%a[g[i+1]]==0)g[i]=g[i+1];        else g[i]=i;    for(int i=1;i<=n;++i)        r[f[i]]=max(r[f[i]],i),        l[g[i]]=min(l[g[i]],i);    for(int i=1;i<=n;++i){        r[i]=max(r[i],r[f[i]]),        l[i]=min(l[i],l[g[i]]);    }    for(int i=1;i<=n;++i)ans=max(ans,r[i]-l[i]+1);    cout<
     
      <
     
    

让我们一起膜拜大佬@