Arithmetic Sequence

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

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

题意：给定一序列和d1，d2.问有多少间隔可以保证存在i，对于每一个j，有j(1≤j<i),bj+1=bj+d1， j(i≤j<n),bj+1=bj+d2.成立。

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int N = ;

 const int oo = 0x3f3f3f3f;

 long long al[N], ar[N], as[N], n;  // al数组存从左边到这个点一直满足的+d1的数有几个，ar是往右边数满足+d2的有几个。

 int main()

 {

     long long d1, d2, i, ans;

     while(~scanf("%lld %lld %lld", &n, &d1, &d2))

     {

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

             scanf("%lld", &as[i]);

         al[] = ar[n] = ;

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

             if(as[i] == as[i-]+d1)

                 al[i] = al[i-]+;

             else al[i] = ;  // 只要间隔，不满足了那么连续的就是1个，它自身

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

         {

             if(as[i]+d2 == as[i+])

                 ar[i] = ar[i+]+;

             else ar[i] = ;

         }

         ans = ;

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

         {

             if(d1 == d2) ans += al[i];  // 如果d1，d2相等，al直接相加

             else ans += al[i]*ar[i];  // if不等，就等于两者相乘，即间隔种类数

         }

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

     }

     return ;

 }

巴特西

Arithmetic Sequence

Arithmetic Sequence

最新文章

热门文章