hdu5400Arithmetic Sequence

//一个序列，两个公差d1,d2
//问有多少个区间使得这个区间存在一个点,它的左边是公差为d1的序列
//它的右边是公差为d2的序列
//直接存入每个点向左和向右延伸的公差长度,乘一下就行
//还有就是注意一下d1=d2的情况
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = 1e5+10 ;
int a[maxn] ;
typedef long long ll ;
ll l[maxn] , r[maxn] ;
int main()
{
    int n , d1 , d2 ;
    while(~scanf("%d%d%d" ,&n , &d1 , &d2))
    {
        for(int i = 1;i <= n;i++)
            scanf("%d" , &a[i]) ;
        ll ans = 0 ;
        if(d1 == d2)
        {
            ll sum = 1;
            for(int i = 2;i <= n;i++)
            if(a[i] == a[i-1] + d1)
            sum++ ;
            else
            {
                ans += (sum+1)*sum/2 ;
                sum = 1 ;
            }
            ans += (sum+1)*sum/2 ;
        }
        else
        {
            l[0] = 0 ;r[n+1] = 0 ;
            for(int i = 1;i <= n;i++)
            if(a[i] == a[i-1] + d1)
            l[i] = l[i-1] + 1 ;
            else l[i] = 1 ;
            for(int i = n;i >= 1;i--)
            if(a[i] == a[i+1] - d2)
            r[i] = r[i+1] + 1 ;
            else r[i] = 1 ;
            for(int i = 1;i <= n;i++)
            ans += l[i]*r[i] ;
        }
        printf("%lld\n" , ans) ;
    }
    return 0 ;
}

hdu5400Arithmetic Sequence

原文：http://blog.csdn.net/cq_pf/article/details/47756077