BestCoder Sequence

　　hdu 　　4908 Bestcoder

Problem Description

Mr Potato is a coder.
Mr Potato is the
BestCoder.

One night, an amazing sequence appeared in his dream. Length
of this sequence is odd, the median number is M, and he named this sequence as
Bestcoder Sequence.

As the best coder, Mr potato has strong
curiosity, he wonder the number of consecutive sub-sequences which are
bestcoder sequences in a given permutation of 1 ~ N.

Input

Input contains multiple test cases.
For each test
case, there is a pair of integers N and M in the first line, and an permutation
of 1 ~ N in the second line.

[Technical Specification]
1. 1
<= N <= 40000
2. 1 <= M <= N

Output

For each case, you should output the number of
consecutive sub-sequences which are the Bestcoder Sequences.

Sample Input

1 1

5 3

4 5 3 2 1

Sample Output

建模好了，很好做。对于满足题意的子串，大于M的个数等于小于M的个数。我们只关心大于小于M这个性质。

我们把大于M的数记作1，小于M的数记作-1，M记作0，则连续的包含M的和为0的子串就是满足题意的子串。

建立模型。我们用数组sum[i]表示1->i 的和。对于大于等于M_ID 的数 i,sum[i],如果sum[j]==sum[i](j<M_id)

则j+1到I为满足题意的子串。

#include"iostream"

#include"cstdio"

#include"cstring"

#include"algorithm"

using namespace std;

const int ms=40000;

int sum[ms+1],a[ms+20000];

int n,m;

void solve()

{

    memset(sum,0,sizeof(sum));

    memset(a,0,sizeof(a));

    int x,i,ans=0,id;

    for(i=1;i<=n;i++)

    {

        scanf("%d",&x);

        sum[i]=sum[i-1];

        if(x==m)

        {

            id=i;

            continue;

        }

        if(x>m)

            sum[i]++;

        else

            sum[i]--;

    }

    for(i=0;i<id;i++)

    {

        a[sum[i]+ms]++;

    }

    for(i=id;i<=n;i++)

        ans+=a[sum[i]+ms];

    printf("%d\n",ans);

    return ;

}

int main()

{

    while(scanf("%d%d",&n,&m)==2)

    {

        solve();

    }

    return 0;

}

巴特西

BestCoder Sequence

最新文章

热门文章