BZOJ 1303: [CQOI2009]中位数图【前缀和】
BZOJ 1303: [CQOI2009]中位数图【前缀和】
Angel_Kitty
发布于 2018-04-09 14:58:41
发布于 2018-04-09 14:58:41
文章被收录于专栏：小樱的经验随笔
1303: [CQOI2009]中位数图
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 2737 Solved: 1698
Description
给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
Input
第一行为两个正整数n和b ，第二行为1~n 的排列。
Output
输出一个整数，即中位数为b的连续子序列个数。
Sample Input
7 4 5 7 2 4 3 1 6
Sample Output
4
HINT
第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6} N<=100000
Source
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1303
思路：
把比b大的定为1，把b小的定为-1，等于b的定为0，这道题就变成了，求在给的数字段里边找到连续的奇数个数，并且和为0，我们用一个cnt数组来记录当前所有数字的和，即cnt[i]=cnt[0]+cnt[1]+......cnt[i],那么只要cnt[i]==0并且i为奇数，肯定满足，但是其他情况也需要考虑，即不是从头开始的，但是有一段的和等于0，这是就得分情况了，如果这一连续的段为奇数，那么肯定符合，如果是偶数就肯定不符合，我们用a数组表示当i为奇数使前i个数的和是否出现过，1为出现过，0 表示未出现，用数组b表示i为偶数时的情况，那么问题来了，如果对于同一个数，a数组里边出现过，b数组里边也出现过，是不是说明了，给定的数字串在某一个奇数区间里边的和为0，那么问题便得到了解决
下面给出AC代码：
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int maxn=100010;
4 int n,t;
5 int a[maxn<<1],b[maxn<<1],cnt[maxn<<1],ans,x,m;
6 inline int read()
7 {
8 int x=0,f=1;
9 char ch=getchar();
10 while(ch<'0'||ch>'9')
11 {
12 if(ch=='-')
13 f=-1;
14 ch=getchar();
15 }
16 while(ch>='0'&&ch<='9')
17 {
18 x=x*10+ch-'0';
19 ch=getchar();
20 }
21 return x*f;
22 }
23 inline void write(int x)
24 {
25 if(x<0)
26 {
27 putchar('-');
28 x=-x;
29 }
30 if(x>9)
31 {
32 write(x/10);
33 }
34 putchar(x%10+'0');
35 }
36 int main()
37 {
38 n=read();
39 t=read();
40 for(int i=1;i<=n;i++)
41 {
42 x=read();
43 if(x>t)
44 {
45 m=1;
46 }
47 else if(x==t)
48 {
49 m=0;
50 }
51 else if(x<t)
52 {
53 m=-1;
54 }
55 cnt[i]+=cnt[i-1]+m;
56 if(cnt[i]==0&&i%2==1)
57 {
58 ans++;
59 }
60 if(i%2==1)
61 {
62 ans+=a[cnt[i]+n];
63 b[cnt[i]+n]++;
64 }
65 else if(i%2==0)
66 {
67 ans+=b[cnt[i]+n];
68 a[cnt[i]+n]++;
69 }
70 }
71 write(ans);
72 return 0;
73 }本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-07-06 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
