TOJ 6121: 学长的情书 ( 二分)
传送门:
6121: 学长的情书
总提交: 79 测试通过:2
描述
抹布收到了一封情书,但是这封情书上只有一串数字,发信人多半是将想要表达的意思隐藏在这串数字里,但是直男抹布怎么看得出来呢。抹布对着这串数字百思不得其解,十分苦恼,当然了,一味的苦恼不是抹布的性格,他决定苦中作乐,他想知道,这串数字中有多少组"优美子序列"。他定义,如果某个连续 的子序列中恰好包含k个偶数数字,就称这个序列为"优美子序列"。
现在你看到抹布竟然对着这样一封有着特殊含义的情书玩起了毫不相干的游戏,你看不下去了,你决定...帮助他解出这个问题。
输入
输入数据多组,以EOF结束。
每组数据第一行,包含两个正整数n,k,表示n个数字,k的含义与描述中相同。(1<=n<=10^5,0<=k<=5*10^4)
接下来一行,包含n个正整数m,每个数字之间用一个空格隔开。(1<=m<=10^5)
数据组数小于110组。
输出
对于每组输入,输出优美子序列的组数,占一行。
样例输入
5 3
2 2 1 2 2
样例输出
2
提示
【样例说明】恰好包含3个偶数的连续子序列只有2个,分别是[2,2,1,2],[2,1,2,2]。
【数据范围】
对于45%的数据,1<=n<=10^3,0<=k<=10^3。
对于90%的数据,1<=n<=10^4,0<=k<=10^4。
对于100%的数据,1<=n<=10^5,0<=k<=5*10^4。
吐槽:
看到2KMS,想了个nlogn的二分去大力莽了。。
思路:
老年人做法
预处理偶数的前缀和。
比如说
样例 2 2 1 2 2
前缀和sum数组是1 2 2 3 4
对每个位置pos,对前缀和数组的操作是对pos之后的位置进行二分查找到sum[pos-1]+k,第一个等于这个数位置posLeft和最后一个等于这个数的位置posRight
差值就是当前位置对答案的贡献:ans += posRight-posLeft+1
trick:
1、当K等于0时候,如果二分写的不好要过滤一下(二分写的好的话可能不用?存疑)
2、ans要用long long
复杂度O(nlogn)
应该有双指针的贡献算法更快(待补)
代码:
#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
int a[],k,n;
int sum[];
int SolveLeft(int begin){
int l = begin,r = n;
int key = sum[begin-] + k;
int ans = ;
while(l <= r){
int mid = (l+r) >> ;
if(sum[mid] >= key){
r = mid-;
ans = mid;
}else{
l = mid+;
}
}
return ans;
}
int SolveRight(int begin){
int l = begin,r = n;
int key = sum[begin-] + k;
int ans = ;
while(l <= r){
int mid = (l+r) >> ;
if(sum[mid] > key){
r = mid-;
}else{
l = mid+;
ans = mid;
}
}
return ans;
} int main(){
while(~scanf("%d%d",&n,&k)){
LL ans = ;
sum[] = ;
for(int i = ; i <= n ; i ++){
scanf("%d",a+i);
a[i] = (a[i]&) ? :;
sum[i] = ;
}
for(int i = ; i <= n ; i ++){
sum[i] = sum[i-]+a[i];
}
for(int i = ; i <= n ; i ++){
int L = SolveLeft(i);
int R = SolveRight(i);
if(R < i) continue; //当K等于0的时候会过滤掉误加
if(L != ){
ans += (R-L+1L);
}
}
cout<<ans<<endl;
}
}
/*
5 3
2 2 1 2 2 6 3
2 2 1 2 1 2 5 0
1 0 1 0 1 5 1
2 2 1 2 2 10 0
1 1 0 1 0 1 1 1 0 0 2 1
1 0 2 0
1 0
*/
最新文章
- linux 安装 nginx 及反向代理配置
- Bootstrap组件之响应式导航条
- php的数据循环 之li的3个类判断
- php截取指定字符串之间的字符串的类
- 学习iOS的博客推荐
- 简单详细的OD破解教程
- bat脚本命令
- 从零开始学习OpenGL ES之一 – 基本概念
- gitlab仓库迁移
- js中var,let,const理解
- ROS机器人程序设计(原书第2版)补充资料 (玖) 第九章 导航功能包集进阶 navigation
- Dynamics CRM2013/2015 插件注册工具登录后无法显示assembly列表问题的解决办法二
- 常用的Arrays类和二维数组以及二分法的介绍
- MySQL5.7: Paging using Mysql Stored Proc
- DSL 系列(2) - 插件的论述与实现
- OneNET麒麟座应用开发之五:获取加速度传感器ADXL345数据
- 8.1 C++输入输出类的层次
- 全网最详细的HA集群的主节点之间的双active,双standby,active和standby之间切换的解决办法(图文详解)
- [C#]记一次解析XML转对象的笔记
- linux环境中安装ftp服务
热门文章
- 比较全面的一个PHP缓存类解析
- 杨柳目-杨柳科-Info-新闻:注意了!杨絮解决有办法了
- 小爬爬4.协程基本用法&;&;多任务异步协程爬虫示例(大数据量)
- Win10系统使用Docker安装oracle并通过Navicat for oracle进行登录
- [asp.net]登录协同工作平台安全解决方式
- python 浮点型(float)
- Flask学习之五 用户登录
- SVN更换新的svn链接
- Getting started with the basics of programming exercises_1
- 认识web前端开发