首页 - 互联网

hdu 4908 BestCoder Sequence 发现M中值是字符串数, 需要预处理

作者: 五速梦信息网
时间: 2026年04月04日 13:41

BestCoder Sequence

Time Limit: ²⁰⁰⁰⁄₁₀₀₀ MS (Java/Others) Memory Limit: ³²⁷⁶⁸⁄₃₂₇₆₈ K (Java/Others)

Total Submission(s): 271 Accepted Submission(s): 112

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 <= 40000
1 <= M <= N

Output

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

Sample Input

Sample Output

1

3

Hint
For the second case, {3},{5,3,2},{4,5,3,2,1} are Bestcoder Sequence.

题目意思是再给出的全排列(1~n每一个数字仅仅出现一次)中,找到一个奇数个的子串,要求子串的中位数(大小排序后正中间的数), 为M;

求这样的子串有多少.

首先要把M这个数左边的串预处理下, 假设遇到大于M的数ji++,然后记录在data[当前位置的奇偶][当前记录的ji] ,假设当前位置的数小于M的数,ji–; 由于ji记录在数组里,所以ji 要价格50000 以保证不会出现负数的情况.

然后再处理右边的串,ji 又一次计数,

ans+data[位置奇偶, 假设两个位置奇偶同样,代表这条串有奇数个元素][-ji 加个符号,找到前面处理过的左串中,能够互补的串,达到大于M的数和小于M的数一样多];

相同加个ji取负数后相同加个 50000,和前面保存一致

#include&lt;stdio.h&gt;

#include&lt;string.h&gt;

int big(int a)

{

return a+50000;

}

int a[50000],ji,data[2][200000];

int main()

{

int n,m,i,j,wei;

int ans;

while(scanf(“%d%d”,&n,&m)!=EOF)

{

	ans=0;

	for(i=1;i&lt;=n;i++)

	{

		scanf(“%d”,&a[i]);

		if(a[i]==m)

			wei=i;

	}

	ji=0;

	memset(data,0,sizeof(data));

	for(i=wei;i&gt;=1;i–)

	{

		if(a[i]&lt;m)

			ji–;

		if(a[i]&gt;m)

			ji++;

		if(i&1)

			data[1][big(ji)]++;

		else

			data[0][big(ji)]++;

	}

	ji=0;

	for(i=wei;i&lt;=n;i++)

	{

		if(a[i]&lt;m)

			ji–;

		if(a[i]&gt;m)

			ji++;

		if(i&1)

			ans+=data[1][big(-ji)];

		else

			ans+=data[0][big(-ji)];

	}

    printf(“%d\n”,ans);

}

return 0;

}