HDU 4908 BestCoder Sequence （哈希）

HDU 4908 BestCoder Sequence （哈希）

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 <= N <= 400001 <= M <= N

Output

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

Sample Input

1 115 34 5 3 2 1

Sample Output

13

题意

给出一个数列，中位数为m，问在这个数列中能找到多少个子连续数列满足中位数为m，且长度为奇数。

思路

我们可以先找到m这个位置，然后向右扩展，如果遇到的数大于m，​​l++​​​，否则​​l--​​​，用​​hashh​​​数组来存储出现 ​​l​​ 这种情况的次数。

然后从m向左扩展，同样的​​l++ l--​​​，如果 ​​hashh[MAXX-l]​​​ 有值，也就是匹配到了之前向右扩展的情况，于是 ​​ans+=hashh[MAXX-l]​​​ ，因为m一定在这个数列里面，所以初始时 ​​hashh[MAXX]=1​​ 。

给数组下标 ​​+MAXX​​ 是因为l的值可能为负数。

AC 代码

#include#include#include#include#include#includeusing namespace std;#include#include#define MAXX 41000int a[MAXX],hashh[MAXX<<1];int main(){ int n,m; while(~scanf("%d%d",&n,&m)) { int k=0,ans=0; for(int i=0; i=0; i--) { if(a[i]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。