hdu(5400)——Arithmetic Sequence（想法題）

題意：

首先，現在給出三個數字n，d1，d2。然後第二行給出n個數字。

然後題目要求的是求這個序列中有幾個區間滿足一下條件之一：

1）這個區間是一個等差數列，且公差為d1或d2；

2）若一個區間為[l,r]，那麼有l<=i<=r，使得[l,i]范圍內是公差為d1的等差數列，[i,r]區間內是公差為d2的等差數列。

*注意，這裡單個數字一定是滿足等差數列的。而且這裡數字最好都使用__int64來保存，因為這個原因我們隊WA了好幾次。

思路：

這裡我設了頭和尾兩個指針，分別用l和r表示。

我用des保存了相鄰兩個數組的差值。

當pos==1時，

1）如果des==d1，那麼只需要改變r指針就好，然後使計數器ans+=r-l+1；

2）如果des==d2，那麼使pos=2，並且同時改變r指針，ans+=r-l+1；

3）如果des!=d1&&des!=d2，那麼使左右指針同時指向當前位置i，ans+=r-l+1（因為要加上它的本身）；

當pos==2時，

1）如果des==d2，那麼同上1

2）des==d1，因為題目說明了d1是不能出現在d2後面的，所以這又算是另外一個區間了，所以使頭指針指向l=i-1，r=i；ans+=r-l+1；同時pos=1；

3）如果des!=d1&&des!=d2，那麼使左指針改變為i就好，因為此時滿足條件的就只有它本身這一個區間了，所以ans++就好。

最後的答案就是ans

#include
#include
#include
#include
#include
using namespace std;
#define maxn 100010
typedef __int64 ll;
ll a[maxn],des[maxn];
int main(){
    int n,d1,d2;
    while(~scanf(%d%d%d,&n,&d1,&d2)){
        memset(a,0,sizeof(a));
        memset(des,0,sizeof(des));
        scanf(%I64d,&a[1]);
        for(int i=2;i<=n;i++){
            scanf(%I64d,&a[i]);
            des[i]=a[i]-a[i-1];		//des數組中保存的是後一個數與前一個數的差值 
        }
        int l=1,r=0;
        int pos=1;
        //以下如果pos==1，那麼說明現在是公差為d1的
		//如果pos==2，那麼說明現在是公差為d2的 
        __int64 ans=1;
        for(int i=2;i<=n;i++){	//從第二個開始判斷 
            if(pos==1){
                if(des[i]==d1){	 
                    r=i;
                    ans+=r-l+1;
                }
                else if(des[i]==d2){
                    pos=2; r=i;
                    ans+=r-l+1;
                }
                else{
                    l=i; r=i;
                    ans+=r-l+1;
                }
            }
            else if(pos==2){
                if(des[i]==d2){
                    r=i; 
                    ans+=r-l+1;
                }
                else{
                    if(des[i]==d1){
                        pos=1;
                        l=i-1;		//這裡注意，因為我們des保存的是a[i]-a[i-1]，所以這裡l應該指向i-1這個位置 
                        r=i;
                        ans+=r-l+1;
                    }
                    else l=i,ans++;
                }
            }
        }
        printf(%I64d
,ans);
    }
}