首页 > 代码库 > hdu 5400 Arithmetic Sequence
hdu 5400 Arithmetic Sequence
hdu 5400 Arithmetic Sequence
分析:
首先预处理出来出ii这个位置向前d_1 d?1的等差序列;
向后d_2 d?2的等差数列能延续到多长,记作l_i,r_i l?i,r?i
假设d_1!=d_2 d?1≠d2,那么枚举中间位置。答案为l_i*r_i l?i?r?i
假设d_1 =d_2 d?1=d?2,枚举開始位置。答案为r_i r?i
代码:
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
const int N=101000;
int n,d1,d2;
int a[N],l[N],r[N];
ll ans;
int main()
{
while (scanf("%d%d%d",&n,&d1,&d2)!=EOF) {
for(int i=0; i<n; i++)
scanf("%d",a+i);
for(int i=0; i<n; i++)
if (i==0||a[i-1]+d1!=a[i])
l[i]=1;
else
l[i]=l[i-1]+1;
for(int i=n-1; i>=0; i--)
if(i==n-1||a[i]+d2!=a[i+1])
r[i]=1;
else
r[i]=r[i+1]+1;
ans=0;
for(int i=0; i<n; i++)
if(d1!=d2)
ans+=(ll)l[i]*r[i];
else
ans+=r[i];
printf("%lld\n",ans);
}
return 0;
}
hdu 5400 Arithmetic Sequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。