bzoj1303[CQOI2008]中位数图 / 乱搞
2024-08-25 06:09:20
题目描述
给出1~n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后,位于中间的数。
输入输出格式
输入格式:
第一行为两个正整数n和b,第二行为1~n的排列。
【数据规模】
对于30%的数据中,满足n≤100;
对于60%的数据中,满足n≤1000;
对于100%的数据中,满足n≤100000,1≤b≤n。
输出格式:
输出一个整数,即中位数为b的连续子序列个数。
输入输出样例
输入样例#1:
7 4
5 7 2 4 3 1 6
输出样例#1:
4 网上有dalao说看到中位数就想到0、-1、1代替,真的好强啊... 那么,我们把输入进来的数分为三类。把比要看成中位数大的数标为1,把比要看成中位数小的数设为-1,把要看成中位数的这个数看做0.并记录这个数的位置。 我们把要看成中位数的这个数记为T
因为合法的序列有三种:完全在T左边的序列,完全在T右边的序列,横跨T(即在T左边也有,右边也有的)的数列。 对于完全在T左边的数列,我们可以这样处理:
既然已经把除T外数列中的其他数搞为1、-1,即知道他们的相对大小。那么我们可以在从T出发向左累加,获得0时就得到了一种合法答案。
对于完全在T右边的数列同理。 对于横跨的数列:
我们可以在向左遍历时顺便求出存当前值有几个的数组(开个桶),有负数怎么办?我们可以统统加上一个较大的数kk,便不会有这种问题。
那么在向右遍历时就可以顺便求出横跨的ans。因为我们用的原理是和为0,那么ans+=f[-tmp+kk] code
#include<bits/stdc++.h>
using namespace std; int kk,n,b,pos,tmp,ans;
int a[],f[]; int main()
{
scanf("%d%d",&n,&b);
kk=n;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>b) a[i]=;
else if(a[i]<b) a[i]=-;
else if(a[i]==b) a[i]=,pos=i;
}
for(int i=pos-;i>=;i--)
{
tmp+=a[i];
if(tmp==) ans++;
f[tmp+kk]++;
}
tmp=;
for(int i=pos+;i<=n;i++)
{
tmp+=a[i];
if(tmp==) ans++;
ans+=f[-tmp+kk];
}
ans++;
printf("%d",ans);
return ;
}
最新文章
- canvas流星月亮星星银河
- K近邻分类法
- PSR规范
- 常见HTTP状态码
- 从浏览器输入url到页面加载完成都发生了什么
- 序列化与反序列化成XML
- [翻译] 为什么Uber的数据库从Postgres 切换到 MySql
- maven3创建多模块web项目
- java 用socket制作一个简易多人聊天室
- 传感器(2)常用api简介及列出当前设备支持的传感器代码
- 我的Android 4 学习系列
- C#自定义配置文件节点
- Linq to Object原理
- 关于Appium android input manager for Unicode 提示信息
- spark常见异常汇总
- zabbix 乱码问题
- FOB cost---从工厂到码头的费用
- python argparse(参数解析)模块学习(二)
- 微信小程序上传图片,视频及预览
- 写给正在入坑linux系统的伙伴