Arithmetic Sequence（构造等差数列）

Arithmetic Sequence

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

Problem Description

A sequence b 1,b 2,⋯,b n are called (d 1,d 2)-arithmetic sequence if and only if there exist i(1≤ i ≤ n) such that for every j(1≤ j <i),b j +1=b j +d 1 and for every j(i ≤ j <n),b j +1=b j +d 2.

Teacher Mai has a sequence a 1,a 2,⋯,a n. He wants to know how many intervals [l ,r](1≤ l ≤ r ≤ n) there are that a l ,a l +1,⋯,a r are (d 1,d 2)-arithmetic sequence.

Input

There are multiple test cases.

For each test case, the first line contains three numbers n ,d 1,d 2(1≤ n ≤105,|d 1|,|d 2|≤1000), the next line contains n integers a 1,a 2,⋯,a n(|a i |≤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

Source

2015 Multi-University Training Contest 9

Recommend

wange2014 | We have carefully selected several similar problems for you: 6373 6372 6371 6370 6369

题意：

定义N个数组成的序列b1、b2、b3、...、bn为(d1, d2)序列

满足：存在一个i 使得 b[j+1] = b[j] + d1(1<=j<i) && b[j] = b[j-1] + d2(i<=j<=N).

思路：构造两个等差数列

定义数组l[i]——为从左到右且以a[i]元素为末尾的等差数列的长度

定义数组r[i]——为从右到左且以a[i]元素为末尾的等差数列的长度

注：以后遇到两端分别连续的情况，还要结合的这一种，就要想到这种方法，标记一下以为端点，同时以为开始的特点。

代码：

 #include<bits/stdc++.h>

    
 using namespace std;
    
 const int maxn=100100;
    
 int main()
    
 {
    
     int a[maxn];
    
     long long l[maxn],r[maxn];
    
     int n,d1,d2;
    
     while(scanf("%d%d%d",&n,&d1,&d2)!=EOF){
    
     for(int i=1;i<=n;i++){
    
         scanf("%d",&a[i]);
    
     }
    
     l[1]=1;
    
     for(int i=2;i<=n;i++){
    
         if(a[i]-a[i-1]==d1){
    
             l[i]=l[i-1]+1;
    
         }
    
         else
    
             l[i]=1;
    
     }
    
     r[n]=1;
    
     for(int i=n-1;i>=1;i--){
    
         if(a[i+1]-a[i]==d2){
    
             r[i]=r[i+1]+1;
    
         }
    
         else r[i]=1;
    
     }
    
     long long ans=0;
    
     if(d1!=d2){
    
         for(int i=1;i<=n;i++){
    
             ans+=l[i]*r[i];
    
         }
    
     }
    
     else{
    
         for(int i=1;i<=n;i++){
    
             ans+=r[i];
    
         }
    
     }
    
     cout<<ans<<endl;
    
     }
    
 }

参考：<>