（模拟）Arithmetic Sequence -- HDU -- 5400

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5400

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

Problem Description

A sequence

-arithmetic sequence.

Input

There are multiple test cases.

For each test case, the first line contains three numbers

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

12 5

代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

#define N 100005
#define LL long long

int a[N], dp[N];

int main()
{
    int n, d1, d2;

    while(scanf("%d%d%d", &n, &d1, &d2)!=EOF)
    {
        int i;

        for(i=1; i<=n; i++)
            scanf("%d", &a[i]);

        memset(dp, 0, sizeof(dp));

        for(i=1; i<n; i++)
        {
            if(a[i+1]==a[i]+d1)
                dp[i+1] = 1;
            else if(a[i+1]==a[i]+d2)
                dp[i+1] = 2;
            else dp[i+1] = 3;
        }

        LL ans=0, tmp=0;

        for(i=1; i<=n; i++)
        {
            if(dp[i]==1)
            {
                if(dp[i-1]==2) tmp = 1;
                else  tmp++;

                ans = ans + tmp +1;
            }
            else if(dp[i]==2)
            {
                tmp++;
                ans = ans + tmp + 1;
            }
            else
            {
                ans ++;
                tmp = 0;
            }
        }

        printf("%lld
", ans);

    }
    return 0;
}

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define N 110000

int a[N];

int main()
{
    int n, i, x, y, d1, d2;

    while(scanf("%d%d%d", &n, &d1, &d2)!=EOF)
    {
        __int64 s1, s2, sum;

        s1 = s2 = sum = 0;
        memset(a, 0, sizeof(a));

        scanf("%d", &x);

        for(i=1; i<n; i++)
        {
            scanf("%d", &y);
            a[i] = y-x;
            x = y;
        }

        for(i=1; i<n; i++)
        {
            if(a[i]==d1)
            {
                if(a[i-1]!=d1)  s1 = 0;

                s1++;
                sum += s1;  ///sum加上当前公差为的d1序列长度
                s2 = 0;     ///s2进行清零
            }
            else if(a[i]==d2)
            {
                s2++;
                sum += s1 + s2;  ///加上公差为d2和前半段为d1后半段为d2的序列长度
            }
            else
                s1 = s2 = 0;
        }

        printf("%I64d
", sum+n);  ///n是只有一个元素的时候
    }

    return 0;
}

（模拟）Arithmetic Sequence -- HDU -- 5400

相关推荐