锐客网

  1. 首页 > it技术 > >

bzoj1303[CQOI2009]中位数图

1303: [CQOI2009]中位数图 Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 1969 Solved: 1264
[ 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 Sample Output 4 HINT 第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}
N<=100000
Source 在不考虑数据范围的情况下，用连续字段和，大概2000以内的数据都能过，但是这题数据居然给到了100000，那么暴力是解决不了问题了。
【bzoj1303[CQOI2009]中位数图】。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
这是一个分外机智的思路。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
把比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，那么问题便得到了解决，详细见代码：

#include #include #include using namespace std; int a[110000*2],b[110000*2],cnt[110000],t,i,j,k,l,m,n; int main() { while(scanf("%d%d",&n,&m)!=EOF) { memset(cnt,0,sizeof(cnt)); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); int ans=0; for(i=1; i<=n; i++) { scanf("%d",&k); if(k>m) l=1; if(k==m) l=0; if(k




    推荐阅读


    上一篇：虚拟机连不上网

    下一篇：抖音视频无水印下载软件，抖音视频批量下载工具