首页 > 代码库 > hdu 4908 BestCoder Sequence 找M为中位数的串的数目, 需要预处理

hdu 4908 BestCoder Sequence 找M为中位数的串的数目, 需要预处理

2024-07-15 15:37:51   220人阅读

BestCoder Sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 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. 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


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<stdio.h>
#include<string.h>
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<=n;i++)
		{
			scanf("%d",&a[i]);
			if(a[i]==m)
				wei=i;
		}
		ji=0;
		memset(data,0,sizeof(data));
		for(i=wei;i>=1;i--)
		{
			if(a[i]<m)
				ji--;
			if(a[i]>m)
				ji++;
			if(i&1)
				data[1][big(ji)]++;
			else
				data[0][big(ji)]++;
		}
		ji=0;
		for(i=wei;i<=n;i++)
		{
			if(a[i]<m)
				ji--;
			if(a[i]>m)
				ji++;
			if(i&1)
				ans+=data[1][big(-ji)];
			else
				ans+=data[0][big(-ji)];	
		}
	    printf("%d\n",ans);
	}
	return 0;
}


联系
我们