P1627 [CQOI2009]中位数 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • LPA20020220
    还没有评论
  • Chemist
    %%%
  • Sagittarius
    %%%%%%%%
  • Chevalier
    %%%%%
  • ecnerwaIa
    还没有评论
  • loneliness
    还没有评论
  • ecnerwaIa
    还没有评论
  • 田大坑
    还没有评论
  • Isonan
    还没有评论
  • 哔哩哔哩
    太强了
作者: distantlight 更新时间: 2017-08-16 11:53  在Ta的博客查看 举报    41  

思路楼下都说了,简单总结下

1.只关心相对大小,所以数字可以转为1,-1,0。要求覆盖b位置的总和为0的连续子序列数量

2.用部分和,只要求左右部分和相等的对数

3.由于部分和的范围是有界的,使用计数排序即可,复杂度O(n)

下面是比较短的代码实现

#include <iostream>
#define N 100005
using namespace std;
long long n,b,ans,c[2][2*N];
int main () {
    cin>>n>>b; c[0][n]=1;
    for (long long i=0,a,s=n,isRight=0;i<n;i++){
        cin>>a;
        if (a!=b) s+=a>b?1:-1;
        c[isRight|=a==b][s]++;
    }
    for (long long i=0;i<2*n;i++,ans+=c[0][i]*c[1][i]);
    cout<<ans<<endl;
    return 0;
}

评论

  • Gamin
    顶你上去233
  • 夜卿羽
    666
  • Akrain
    %%%%
  • Mosher
    想一块去了
  • Mosher
    这里的mp,我在代码是当个桶的
  • 永远不懂RE原因
    zhutier不也是把它当桶吗
  • 花花公纸他爹
    复杂度从O(n)变成了O(nlog n)
  • zhutier
    昂?(懵
  • you_xiao
    为什么不会减成负数???
  • zhutier
    @you_xiao 会减成负数啊QAQ所以才用的map
作者: zhutier 更新时间: 2018-09-03 21:16  在Ta的博客查看 举报    27  

以该数为中心,向右for一遍有多少个大于/小于该数的数

大于就sumr++ 小于就--(因为是中位数,大于他的和小于他的数的数量一样)

然后每次以sumr为下标的数++

因为sumr可能小于零

并且我比较懒

所以就开了一个map

万能的map!

所以就直接mp[sumr]++;

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
map<int,int> mp;
int n,b,a[100005],q,suml,sumr;
long long ans;
int main(){
    scanf("%d%d",&n,&b);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]==b) q=i;
    }
    for(int j=q;j<=n;j++){
        if(a[j]>b) sumr++;
        if(a[j]<b) sumr--;
        mp[sumr]++;
    }
    for(int i=q;i>=1;i--){
        if(a[i]>b) suml++;
        if(a[i]<b) suml--;
        ans+=mp[0-suml];
    }
    printf("%lld",ans);
} 

与其他题解的区别大概在于比较懒

评论

  • qqvq
    参考~~抄~~了别人的博客要注明啊
  • 夜卿羽
    为什么要加偏移量
  • King_of_gamers
    你确定清新脱俗??
  • HenryHuang
    这是6102年写的呀老哥们
作者: 朝田诗乃  更新时间: 2016-11-14 18:47  在Ta的博客查看 举报    24  

搞个清新脱俗的算法

把中位数出现的位置设为pos,比中位数大的设为1,小的设为-1.

lsum[i]表示i到pos的和,即1的个数和-1的个数差

rsum[i]表示pos到i的和,同理。

l[sum[i]]表示pos左边和为sum出现的次数

r[sum[i]]表示pos右边和为sum出现的次数

由于c++数组不能开负下标,所以需要向右偏移n

如果l[i]=r[-i]就可以将ans+=l[i]*r[-i].

#include <iostream>
#include <cstdio>
using namespace std;
int b,n,a[400001],pos,x,sum[200001],ans=0;
int l[400001],r[400001];
int main()
{
    //freopen("median.in","r",stdin);
    //freopen("median.out","w",stdout);
    scanf("%d%d",&n,&b);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(x==b){pos=i;a[i]=0;}
        else
        if(x>b)a[i]=1;
        else a[i]=-1;
    }
    l[n]=1;r[n]=1;//l[0+n]=1;r[0+n]=1;0出现1次 
    for(int i=pos-1;i>=1;i--)
        {sum[i]=sum[i+1]+a[i];l[sum[i]+n]++;}
    for(int i=pos+1;i<=n;i++)
        {sum[i]=sum[i-1]+a[i];r[sum[i]+n]++;}
    for(int i=-n+n;i<=n-1+n;i++)
        ans+=l[i]*r[n-i+n];
    printf("%d",ans);
}

评论

  • yuy_
    tql%%%
  • Cesare
    orz
  • Asurx星痕
    大佬的图是用什么画的啊
  • 永远不懂RE原因
    顶上去
作者: Heartlessly 更新时间: 2019-02-13 19:52  在Ta的博客查看 举报    15  

Description:

给定长度为 $n$ 的序列,求有多少奇数长度的序列中位数为 $b$ 。


Solution:

因为所求的是中位数,所以考虑改变原序列。把大于 $b$ 的数全部变为 $1$,小于 $b$ 的数变为 $-1$,等于 $b$ 则为 $0$。问题就变为求存在几个包含 $b$ 的区间和为 $0$ 。我们假设 $tmp$ 为 $b$ 的下标,原数组为 $x$,新数组为 $a$ 。

Sample Input:

7 4
5 7 2 4 3 1 6 

Example:

能使结果成立的区间分别为 $[1,5]$ , $[1,7]$ , $[2,4]$ , $[4,4]$。

接下来我们建造两个桶,分别计数 $tmp$ 左边的后缀和与右边的前缀和,假设左边的后缀和为 $l$,右边的前缀和为 $r$ 。$l[i]/r[i]$ 表示从点 $i$ 向右/向左 到点 $tmp$ 为止 (比 $b$ 大的数的数量 - 比 $b$ 小的数的数量) 出现的次数。还是拿样例来说:

通过观察上图,我们能够发现,左边的数 $x$ 可以与右边的每一个 $-x$ 进行匹配。通过乘法原理,该值即为 $l[x] \times r[-x]$,由题意可知 $-10^5 \le x \le 10^5$,遍历所有的 $x$ 即可,最终答案为 $\sum_{i=min}^{max}l[i] \times r[-i]$ 。

值得注意的是,$l[0]$ 和 $r[0]$ 的初始值为 $1$,因为 $b$ 是需要被算入的。当然,桶的下标不能是负数,所以我在每次操作时都加上了一个很大的数,即数据最大值 —— $10^5$,也可以用 $STL$ 中的 $map$ 解决问题,时间复杂度为 $O(n)$ 。


Code

/*
Language:C++
Author:xuxing
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template < class T > inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    x = f ? -x : x;
}

const int maxN = 1e5;

LL n, b, x, tmp, sum, ans, a[maxN + 10], l[maxN << 2], r[maxN << 2];

int main() {
    read(n), read(b);
    for (LL i = 1; i <= n; i++) { read(x); if (x == b) tmp = i; else a[i] = x > b ? 1 : -1; }//初始化
    l[maxN] = 1, r[maxN] = 1;
    for (LL i = tmp - 1; i >= 1; i--) { sum += a[i]; l[sum + maxN]++; }//后缀和统计
    sum = 0;
    for (LL i = tmp + 1; i <= n; i++) { sum += a[i]; r[sum + maxN]++; }//前缀和统计
    for (LL i = 0; i <= (maxN << 1); i++) { if (l[i] && r[(maxN << 1) - i]) ans += l[i] * r[(maxN << 1) - i]; }//累加答案
    printf("%lld\n", ans);
    return 0;
}

评论

  • 橙子汁
    还没有评论
  • Chevalier
    棒!
  • paiTD
    qwq
作者: eros1on 更新时间: 2018-01-28 22:00  在Ta的博客查看 举报    15  
题目传送门

思路

标记一遍相对大小,大的标1,小的标-1。只要连续 n 项和为0,就能满足题目条件。

首先一遍找到中位数位置 pos,放个数组 flag 标记查找中的数与目标中位数的相对大小:

1 -> 比中位数大

-1 -> 比中位数小

0 -> 找到中位数!标记pos

还是举个实例吧……

数组:1 1 -1 -1 -1 pos 1 -1 1

然后从 (pos - 1) 走一遍到1,也就是反过来。再拿一个变量 sum 标记每往左走一个时数组 flag 这一项与这之前的项之和。怎么标?用哈希的方法!(开个数组 f )那万一 sum 值为负怎么办?数组的下标可没有负的!凉拌~ 把所有 sum 值统统加上一个足够大的值 "KEY" 。妈妈再也不用担心下标的值为负啦!

这时的 sum 数组:-1 -2 -3 -2 -1

这时的 f 数组:f [ -1 + KEY ] = 2 ; f [ -2 + KEY ] = 2 ; f [ -3 + KEY ] = 1 ;

做完这些以后,最后从 (pos + 1) 走一遍到 n ,正着走。和上边一样,记录 sum 值。不过这次得多一个步骤——每次要找 pos 左边的对应值。

从 pos 向右

  1. sum=1 -> 左边 sum=-1 -> 两次 ∴ ans+=2;

  2. sum=0 -> 左边 sum=0 -> 无

  3. sum=1 -> 左边 sum=-1 -> 两次 ∴ ans+=2;

最后输出 ans 即可。

C++ 代码如下:

#include <cstdio>//头文件
#include <cstdlib>//头文件
using namespace std;//命名空间
#define KEY 100001//定义一个足够大的数
int n,b,pos,a[100010],flag[100010],f[200010],s,ans;
int main(){
    scanf("%d%d",&n,&b);//输入
    for(int i=1;i<=n;i++){//第一次循环
        scanf("%d",&a[i]);
        if(a[i]==b) pos=i;//就是中位数
        else if(a[i]>b) flag[i]=1;//大的标1
        else flag[i]=-1;//小的标-1
    }
    for(int i=pos-1;i>=1;i--){//第二次循环
        s+=flag[i];//计算此次sum值
        f[s+KEY]++;
        if(s==0) ans++;//找到满足题意只在 pos 左侧的连续子序列!
    }
    s=0;//为第三次循环的累加做准备
    for(int i=pos+1;i<=n;i++){//第三次循环
        s+=flag[i];//计算此次sum值
        if(s==0) ans++;//找到满足题意只在 pos 右侧的连续子序列!
        ans+=f[-s+KEY];
    }
    printf("%d\n",++ans);//还少一次只由 pos 自己组成的连续子序列(也满足条件!)
    return 0;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。