首页 > 代码库 > BestCoder Sequence

BestCoder Sequence

2024-07-16 23:57:14   223人阅读

　　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
1
5 3
4 5 3 2 1
 


Sample Output
1
3
 
 
建模好了，很好做。对于满足题意的子串，大于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;}

 

 


联系
我们