首页 > 代码库 > BestCoder Sequence
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.
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
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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。