Arithmetic Sequence

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1445 Accepted Submission(s): 632

Problem Description

A sequence b1,b2,⋯,bn are called (d1,d2)-arithmetic sequence if and only if there exist i(1≤i≤n) such that for every j(1≤j<i),bj+1=bj+d1 and for every j(i≤j<n),bj+1=bj+d2.

Teacher Mai has a sequence a1,a2,⋯,an. He wants to know how many intervals [l,r](1≤l≤r≤n) there are that al,al+1,⋯,ar are (d1,d2)-arithmetic sequence.

Input

There are multiple test cases.

For each test case, the first line contains three numbers n,d1,d2(1≤n≤105,|d1|,|d2|≤1000), the next line contains n integers a1,a2,⋯,an(|ai|≤109).

Output

For each test case, print the answer.

Sample Input

5 2 -2
0 2 0 -2 0
5 2 3
2 3 3 3 3

Sample Output

12
5

Author

xudyh

对每个数先预处理出左右能够达到的最远距离。然后当d1!=d2时,用乘法原理得到区间数(左边有l[i]个区间,右边有r[i]个区间,左右就是l[i]*r[i]个区间)

当d1==d2 时,左右会算重，只算左边就好了。

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <queue>

#include <algorithm>

using namespace std;

typedef long long LL;

const int N = ;

int a[N];

LL l[N],r[N],ans; ///l[i]记录第i个数左边与其成方差为d1的数的个数,r[i]记录第i个数右边与其方差为

                  ///d2的数的个数(包括自身)

int main()

{

    int n,d1,d2;

    while(scanf("%d%d%d",&n,&d1,&d2)!=EOF){

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

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

        }

        l[] = ,r[n]=;

        ans = ;

        for(int i=;i<=n;i++){ ///预处理

            if(a[i]==a[i-]+d1){

                l[i] = l[i-]+;

            }else l[i] = ;

        }

        for(int i=n-;i>=;i--){

            if(a[i]+d2==a[i+]){

                r[i] = r[i+]+;

            }else r[i]=;

        }

        if(d1==d2){

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

            ans+=l[i];

        }

        }

        else

            for(int i=;i<=n;i++){ ///乘法原理

           // printf("%lld %lld\n",l[i],r[i]);

            ans+=l[i]*r[i];

        }

        printf("%lld\n",ans);

    }

}

巴特西

hdu 5400(思路题)

Arithmetic Sequence

最新文章

热门文章