牛客挑战赛42 A-小睿睿的序列

前言

初，遇题甚恐，不知何以解之。一暴以试，得AC，作此篇

分析

1. 别学数据结构学傻了
2. 我们对于每一个点，可以向左扩展最长能满足条件的区间，然后再向右扩展。但是如果不作些许操作，万一这个序列是10000个1，这样跑就是n^2，直接飞起(但是数据不太强，也可以过)。于是可以记录一个lm[i],rm[i]。

   lm[i]:下标i的数向左扩展的最远点的下标
   rm[i]:下标i的数向右扩展的最远点的下标

3. 原因就是，a|b,b|c,则a|c,就像我们当前求i点向左扩展，找到了j点，且a[j]%a[i]=0。那么满足a[k]%a[j]=0的点也一定满足a[k]%a[i]=0,所以这个时候就可以直接跳到lm[j]，然后接着向左找。向右同理。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n;
int a[N],l[N],r[N],way[N];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);

int ans=0;
for (int i=1;i<=n;i++)
{
    l[i]=i;
    for (int j=i-1;j;)
    {
        if(a[j]%a[i]) break;
        l[i]=l[j];j=l[j]-1;
    }
}//向左找

for (int i=n;i>=1;i--)
{
    r[i]=i;
    for (int j=i+1;j<=n;)
    {
        if(a[j]%a[i]) break;
        r[i]=r[j];j=r[j]+1;
    }
}//向右找
for (int i=1;i<=n;i++) ans=max(ans,r[i]-l[i]);

int num=0;
for (int i=1;i<=n;i++)
    if(r[i]-l[i]==ans&&way[num]!=l[i]) way[++num]=l[i];
//这里注意判重
printf("%d\n",num);

return 0;
}