程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDOJ 5400 Arithmetic Sequence 暴力枚舉

HDOJ 5400 Arithmetic Sequence 暴力枚舉

編輯：關於C++

Arithmetic Sequence

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

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≤jand for every j(i≤j.

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

Sample Output

12
5

Author xudyh
Source 2015 Multi-University Training Contest 9

/* ***********************************************
Author        :CKboss
Created Time  :2015年08月18日 星期二 12時21分22秒
File Name     :1005.cpp
************************************************ */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

using namespace std;

typedef pair pII;
typedef long long int LL;
const int maxn=100100;
const int INF=0x3f3f3f3f;

int n,d1,d2;
int a[maxn];
LL ans;

vector up,down;

void bd2()
{        
    LL aaa=n-1;
    for(int i=0,sz=up.size();i1)
            {
                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 duan
        for(int i=0,sz=up.size();idown[j].first) j++;
				else if(up[i].second