Arithmetic SequenceTime Limit: 4000/2000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 382Accepted Submission(s): 196
Problem Description
A sequenceare called-arithmetic sequence if and only if there existsuch that for everyand for every.Teacher Mai has a sequence. He wants to know how many intervalsthere are that-arithmetic sequence.
Input
There are multiple test cases.For each test case, the first line contains three numbers, the next line contains.
Output
For each test case, print the answer.
Sample Input
5 2 -20 2 0 -2 05 2 32 3 3 3 3
Sample Output
125
Author
xudyh
Source
/* ***********************************************Author:CKbossCreated Time :2015年08月18日 星期二 12时21分22秒File Name:1005.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>using namespace std;typedef pair<int,int> pII;typedef long long int LL;const int maxn=100100;const int INF=0x3f3f3f3f;int n,d1,d2;int a[maxn];LL ans;vector<pII> up,down;void bd2(){LL aaa=n-1;for(int i=0,sz=up.size();i<sz;i++){pII pi=up[i];LL dur=pi.second-pi.first+1;aaa+=dur*(dur-1)/2;}cout<<aaa<<endl;}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);while(scanf("%d%d%d",&n,&d1,&d2)!=EOF){ans=n;up.clear(); down.clear();/// one duanint left=-1,right=-1;int Left=-1,Right=-1;bool cl=false;bool Cl=false;for(int i=1;i<=n;i++)scanf("%d",a+i);a[n+1]=INF; n++;for(int i=1;i<=n;i++){if(i>1){int ca=a[i]-a[i-1];if(ca==d1){if(left==-1){left=i-1; right=i; cl=true;}else right=i;}else{if(cl==true){up.push_back(make_pair(left,right));left=right=-1;cl=false;}}}if(i>1){int ca=a[i]-a[i-1];if(ca==d2){if(Left==-1){Left=i-1; Right=i; Cl=true;}else Right=i;}else{if(Cl==true){down.push_back(make_pair(Left,Right));Left=Right=-1;Cl=false;}}}}if(d1==d2){bd2();continue;}/// single duanfor(int i=0,sz=up.size();i<sz;i++){pII pi=up[i];LL dur=pi.second-pi.first+1;ans+=dur*(dur-1)/2;}for(int i=0,sz=down.size();i<sz;i++){pII pi=down[i];LL dur=pi.second-pi.first+1;ans+=dur*(dur-1)/2;}/// double duanfor(int i=0,j=0,sz1=up.size(),sz2=down.size();i<sz1&&j<sz2;){if(up[i].second==down[j].first){LL duan1=up[i].second-up[i].first;LL duan2=down[j].second-down[j].first;ans+=duan1*duan2;i++; j++;}else{if(up[i].second>down[j].first) j++;else if(up[i].second<down[j].first) i++;}}printf("%lld\n",ans);}return 0;}
版权声明：来自: 码代码的猿猿的AC之路
，妩媚动人，让我感受到了大自然的神奇。
