hdu 5328 Problem Killer（杭电多校赛第四场）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5328

题目大意：找到连续的最长的等差数列or等比数列。

解题思路：1、等差等比的性质有很多。其中比较重要的一个就是解题关键：如a[i-2],a[i-1],a[i],a[i+1]这个序列。a[i-2],a[i-1],a[i]是等差数列，a[i-1],a[i],a[i+1]也是等差数列。那么a[i-2],a[i-1],a[i],a[i+1]就是等差数列。

2、等比数列也是一样的~~只要根据这个性质就可以把整个序列查抄一遍，时间复杂度达到O(n);

3、还有一个就是如果是等差数列就满足2*a[i-1]=a[i]+a[i-2];等比的话满足a[i-1]*a[i-1]=a[i]*a[i-2]。

详见代码。

#include <iostream>
#include <cstdio>
#include <algorithm> using namespace std; int ans,n;
long long a[]; void Find()
{
int i;
//cout<<ans<<endl;
int l=;
for (i=; i<=n; i++)
{
if (a[i-]*!=a[i-]+a[i])
l=i-;
ans=max(ans,i-l+);
}
l=; for (i=; i<=n; i++)
{
long long L=a[i-]*a[i-];
long long R=a[i]*a[i-];
//cout<<L<<" "<<R<<endl;
if (L!=R)
l=i-;
ans=max(ans,i-l+);
}
printf ("%d\n",ans);
} int main()
{
int t;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for (int i=; i<=n; i++)
{
scanf("%lld",&a[i]);
}
ans=min(n,);
Find();
}
return ;
}