寻找最美的你(select)

Time Limit:2000ms Memory Limit:128MB

题目描述

这个问题是这样的，如果一个区间[L,R]存在一个数ai，使得这个数是这个区间所有数的约数，那么[L,R]这段区间，是一段好区间。

现在，LYK想知道最长的好区间的长度是多少，并且它想知道最长的好区间具体的位置，如果有多个，从小到大输出它们的左端点。

输入格式(select.in)
第一行一个数n，表示有n个这样的数字。

第二行n个数ai。

输出格式(select.out)

第一行两个数sum,len。其中sum表示有sum个最长的好区间，len表示最长的好区间的长度。

第二行sum个数，从小到大输出，表示所有最长好区间的左端点。

输入样例

4 6 9 3 6

输出样例

1 4

样例解释：

有一个最长的好区间[2,5]。

数据范围

对于40%的数据n<=100。

对于60%的数据n<=3000。

对于80%的数据n<=30000。ai<=1000。

对于100%的数据1<=n<=300000，1<=ai<=1000000。ai以一定方式随机。

　去搜就行，但要看怎么搜才能不超时。

　　从左向右枚举约数，向左向右搜，搜完后跳到r+1开始搜，这样时间复杂度就降下来了。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<math.h>

#include<vector>

using namespace std;

int n,a[];

int l,r;

int len,cnt,ll[];

int main()

{

    freopen("select.in","r",stdin);freopen("select.out","w",stdout);

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        scanf("%d",&a[i]);

     for(int i=;i<=n;i++)

     {

         for(l=i-;l>=;l--)    if(a[l]%a[i]!=)    break;l++;

         for(r=i+;r<=n;r++)    if(a[r]%a[i]!=)    break;r--;

         if(r-l+>len)    len=r-l+,ll[cnt=]=l;else

         if(r-l+==len)    ll[++cnt]=l;

         i=r;

     }

    printf("%d %d\n",cnt,len);

    for(int i=;i<=cnt;i++)

    printf("%d ",ll[i]);

    return ;

}

巴特西

寻找最美的你(select)

最新文章

热门文章