首页 > 代码库 > BZOJ 1303: [CQOI2009]中位数图【前缀和】
BZOJ 1303: [CQOI2009]中位数图【前缀和】
1303: [CQOI2009]中位数图
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 2737 Solved: 1698
[Submit][Status][Discuss]
Description
给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
Input
第一行为两个正整数n和b ，第二行为1~n 的排列。
Output
输出一个整数，即中位数为b的连续子序列个数。
Sample Input
7 4
5 7 2 4 3 1 6
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 }
BZOJ 1303: [CQOI2009]中位数图【前缀和】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。