[ Nowcoder Contest 175 #B ] 区间

\(\\\)

\(Description\)

给出一个长度为\(N\)的序列\(A[1]...A[N]\)，定义一个合法区间 \([L,R]\) 当且仅当区间\(GCD\) 在这个区间内，求最长合法区间长度。

\(N\in [1,4\times 10^{6}]\)

\(\\\)

\(Solution\)

考虑以每一个数作为区间\(GCD\)的答案\((\)下面称作“中心”\()\)，答案区间画在数轴上是什么样的。

一定是由若干个大区间，然后一些小区间都被大区间完全包含，大区间有交，但是都不会越过中心。

只考虑一个位置\(i\)到它右边的数所构成的合法区间。

假如他的右区间可以扩展到\(j\)，那么这\(j-i\)个数的右端点一定\(\le\ i\) 处的答案。

因为显然这\(j-i\) 个数字都是 \(i\) 的倍数，若他们还能向右扩展，则 \(i\) 的答案也能向右扩展。

显然从每一个位置向右扩展复杂度是\(N^2\)的，但是考虑这\(j-i\)个点的左端点显然不会越过\(i\)，右端点答案显然不会越过\(i\) 对应的右端点，所以直接把这些点的右端点设为\(i\) 的右端点并不会出锅。

正反扫描一遍区间长度取 \(max\) 就是答案。

\(\\\)

\(Code\)

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define R register

#define gc getchar

#define N 4000010

using namespace std;

typedef long long ll;

inline ll rd(){

  ll x=0; bool f=0; char c=gc();

  while(!isdigit(c)){if(c=='-')f=1;c=gc();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}

  return f?-x:x;

}

ll n,a[N];

int res,ans[N];

int main(){

  n=rd();

  for(R int i=1;i<=n;++i) a[i]=rd();

  for(R int i=1,r=1;i<=n;++i){

    if(r<i) r=i;

    while(r<n&&a[r+1]%a[i]==0) ++r;

    ans[i]=r;

  }

  for(R int i=n,l=n;i>0;--i){

    if(l>i) l=i;

    while(l>1&&a[l-1]%a[i]==0) --l;

    res=max(res,ans[i]-l+1);

  }

  printf("%d",res);

  return 0;

}

巴特西

[ Nowcoder Contest 175 #B ] 区间

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章