CodeForces - 359D D. Pair of Numbers

66 阅读 0 评论 44 点赞

我是靠谱客的博主陶醉皮卡丘，最近开发中收集的这篇文章主要介绍CodeForces - 359D D. Pair of Numbers，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Simon has an array a1, a2, ..., an, consisting of n positive integers. Today Simon asked you to find a pair of integers l, r (1 ≤ l ≤ r ≤ n), such that the following conditions hold:

there is integer j (l ≤ j ≤ r), such that all integers al, al + 1, ..., ar are divisible by aj;
value r - l takes the maximum value among all pairs for which condition 1 is true;

Help Simon, find the required pair of numbers (l, r). If there are multiple required pairs find all of them.

Input

The first line contains integer n (1 ≤ n ≤ 3·105).

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 106).

Output

Print two integers in the first line — the number of required pairs and the maximum value of r - l. On the following line print all l values from optimal pairs in increasing order.

Note

In the first sample the pair of numbers is right, as numbers 6, 9, 3 are divisible by 3.

In the second sample all numbers are divisible by number 1.

In the third sample all numbers are prime, so conditions 1 and 2 are true only for pairs of numbers (1, 1), (2, 2), (3, 3), (4, 4), (5, 5).

题意： n个数找出一个尽量长的区间l和r 使得l和r中的一个数可以整除区间里的所有数

输出：

区间的个数（如果最长区间有多个则输出多个）区间的长度-1

区间的左边界

思路：枚举每一个数的左边界和右边界，但是根据数据范围可以得出不可以用n方的算法，会超时，所以在处理左右边界可以优化一下。其他的就比较简单了。下面贴上两种代码

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define N 300005

using namespace std;

int a[N],ans[N];

int main()
{
	int i,l,r,n;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	int cnt=0;
	int len=0;
	for(i=1;i<=n;)
	{
		l=i;
		r=i;
		while(l>=1&&a[l]%a[i]==0) l--;
		while(r<=n&&a[r]%a[i]==0) r++;
		l++;
		r--;
		//printf("left : %d right : %dn",l,r);
		i=r+1;
		int num=r-l;
		if(num==len) ans[++cnt]=l;
		else if(num>len)
		{
			cnt=0;
			len=num;
			ans[++cnt]=l;
		}
	}
	printf("%d %dn",cnt,len);
	for(i=1;i<=cnt;i++)
	{
		if(i==cnt) printf("%dn",ans[i]);
		else printf("%d ",ans[i]);
	}
	return 0;
}

第二种最后输出要注意一下.

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define N 300005

using namespace std;

int a[N],ans[N],ll[N],rr[N];
int n;

void init()
{
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		ll[i]=rr[i]=i;
	}
	return ;
}

void output()
{
	int i,j,left,right;
	int Ans=0,len=0;
	for(i=1;i<=n;++i)
    {
        left=ll[i];right=rr[i];
        if(right-left==len)ans[++Ans]=left;
        if(right-left>len)len=right-left,ans[Ans=1]=left;
    }
    int xllend3=0;
    sort(ans+1,ans+Ans+1);
    for(i=1;i<=Ans;++i)if(ans[i]!=ans[i-1])++xllend3;
    printf("%d %dn%d",xllend3,len,ans[1]);
    for(i=2;i<=Ans;++i)if(ans[i]!=ans[i-1])printf(" %d",ans[i]);
    printf("n");
}

int main()
{
	int i,j,l,r;
	init();
	int maxx=0;
	int cnt=0;
	for(int i=1;i<=n;++i)for(;ll[i]>1&&a[ll[i]-1]%a[i]==0;)ll[i]=ll[ll[i]-1];
    for(int i=n;i>=1;--i)for(;rr[i]<n&&a[rr[i]+1]%a[i]==0;)rr[i]=rr[rr[i]+1];
	output();
	return 0;
}