2015多校联合训练第一场Assignment(hdu5289)三种解法

2024-09-07 18:32

本文主要是介绍2015多校联合训练第一场Assignment(hdu5289)三种解法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目大意:给出一个数列,问其中存在多少连续子序列,子序列的最大值-最小值< k
这题有三种解法:
1:单调队列,时间复杂度O(n)
2:RMQ+二分,时间复杂度O(nlogn)
3:RMQ+贪心,时间复杂度O(nlogn)

一:RMQ+二分
RMQ维护最大值,最小值,枚举左端点i,二分找出最远的符合的右端点j,答案就是ans += j - i+1;(手推一下就知道)
比如1 2 3
含有i的有三种
1
1 2
1 2 3
其它的2,2 3,3下面i=2的时候会算的,所以每次加j-i+1就行

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;int  maxsum[100000][30];
int minsum[100000][30];int a[100000];
int n,k;
void rmq_init()
{for(int j = 1; (1<<j) <= n; ++j)for(int i = 1; i + (1<<j) - 1 <= n; ++i){maxsum[i][j] = max(maxsum[i][j-1],maxsum[i+(1<<(j-1))][j-1]); minsum[i][j] = min(minsum[i][j-1],minsum[i+(1<<(j-1))][j-1]);}}int query(int l, int r)
{int k = log2(r-l+1);int Max = max(maxsum[l][k], maxsum[r-(1<<k)+1][k]);int Min = min(minsum[l][k], minsum[r-(1<<k)+1][k]);return Max - Min;
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&k);for(int i = 1; i <= n;++i){scanf("%d",a+i);maxsum[i][0] = minsum[i][0] = a[i];}rmq_init();long long  ans = 0;int l , r;for(int i = 1; i <= n; ++i){l = i , r = n;while(l <= r){int mid = (l+r)/2;int cha = query(i,mid);if(cha < k) l = mid+1;else r = mid - 1;}ans += l - i;}printf("%lld\n",ans);}return 0;
}

二:单调队列
用单调队列维护最大值最小值,双指针,第一个第二个指针初始指向第一个数据,第一个指针按顺序不断向队尾添加数据,当最大值最小值的差大于等于k后,就意味着新添加的这个不能作用于当前第二个指针的位置,也就能计算出,以第二个指针位置开始的连续子序列的个数,最后统计总和。

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std ;
#define LL long long
deque <LL> Max , Min ;
//单调队列,Max最大值,Min最小值
LL a[100010] ;
int main()
{int T , n , i , j ;LL k , ans ;scanf("%d", &T) ;while( T-- ){scanf("%d %I64d", &n, &k) ;for(i = 0 ; i < n ; i++)scanf("%I64d", &a[i]) ;while( !Max.empty() ) Max.pop_back() ;while( !Min.empty() ) Min.pop_back() ;for(i = 0 , j = 0 , ans = 0; i < n ; i++)  //i在前,j在后{while( !Max.empty() && Max.back() < a[i] ) Max.pop_back() ;Max.push_back(a[i]) ;while( !Min.empty() && Min.back() > a[i] ) Min.pop_back() ;Min.push_back(a[i]) ;while( !Max.empty() && !Min.empty() && Max.front() - Min.front() >= k ){ans += (i-j) ;if( Max.front() == a[j] ) Max.pop_front() ;if( Min.front() == a[j] ) Min.pop_front() ;j++ ;}}while( j < n ){ans += (i-j) ;j++ ;}printf("%lld\n", ans) ;}return 0 ;
}

三:RMQ+贪心
这种枚举右端点,贪心选取右端点(类似尺取法)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;int  maxsum[100000][30];
int minsum[100000][30];int a[100000];
int n,m;
void rmq_init()
{for(int j = 1; (1<<j) <= n; ++j)for(int i = 1; i + (1<<j) - 1 <= n; ++i){maxsum[i][j] = max(maxsum[i][j-1],maxsum[i+(1<<(j-1))][j-1]);minsum[i][j] = min(minsum[i][j-1],minsum[i+(1<<(j-1))][j-1]);}}int query(int l, int r)
{int k = log2(r-l+1);int Max = max(maxsum[l][k], maxsum[r-(1<<k)+1][k]);int Min = min(minsum[l][k], minsum[r-(1<<k)+1][k]);return Max - Min;
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i = 1; i <= n; ++i){scanf("%d",a+i);maxsum[i][0] = minsum[i][0] = a[i];}rmq_init();long long  ans = 0;int k=1;for(int i=1; i<=n; i++){while(query(k,i)>=m&&k<i)k++;ans+=(i-k+1);}printf("%lld\n",ans);}return 0;
}

下面分别是三种算法运行时间(3,2,1)
可见时间效率单调队列最好(405ms),贪心+rmq(733ms)次之,二分+rmq(1216ms)最差
这里写图片描述

这篇关于2015多校联合训练第一场Assignment(hdu5289)三种解法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1145824

相关文章

从入门到精通MySQL联合查询

《从入门到精通MySQL联合查询》:本文主要介绍从入门到精通MySQL联合查询,本文通过实例代码给大家介绍的非常详细,需要的朋友可以参考下... 目录摘要1. 多表联合查询时mysql内部原理2. 内连接3. 外连接4. 自连接5. 子查询6. 合并查询7. 插入查询结果摘要前面我们学习了数据库设计时要满

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java继承映射的三种使用方法示例

《Java继承映射的三种使用方法示例》继承在Java中扮演着重要的角色,它允许我们创建一个类(子类),该类继承另一个类(父类)的所有属性和方法,:本文主要介绍Java继承映射的三种使用方法示例,需... 目录前言一、单表继承(Single Table Inheritance)1-1、原理1-2、使用方法1-

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

java对接第三方接口的三种实现方式

《java对接第三方接口的三种实现方式》:本文主要介绍java对接第三方接口的三种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录HttpURLConnection调用方法CloseableHttpClient调用RestTemplate调用总结在日常工作

SpringBoot实现接口数据加解密的三种实战方案

《SpringBoot实现接口数据加解密的三种实战方案》在金融支付、用户隐私信息传输等场景中,接口数据若以明文传输,极易被中间人攻击窃取,SpringBoot提供了多种优雅的加解密实现方案,本文将从原... 目录一、为什么需要接口数据加解密?二、核心加解密算法选择1. 对称加密(AES)2. 非对称加密(R

基于Go语言实现Base62编码的三种方式以及对比分析

《基于Go语言实现Base62编码的三种方式以及对比分析》Base62编码是一种在字符编码中使用62个字符的编码方式,在计算机科学中,,Go语言是一种静态类型、编译型语言,它由Google开发并开源,... 目录一、标准库现状与解决方案1. 标准库对比表2. 解决方案完整实现代码(含边界处理)二、关键实现细

MySQL精准控制Binlog日志数量的三种方案

《MySQL精准控制Binlog日志数量的三种方案》作为数据库管理员,你是否经常为服务器磁盘爆满而抓狂?Binlog就像数据库的“黑匣子”,默默记录着每一次数据变动,但若放任不管,几天内这些日志文件就... 目录 一招修改配置文件:永久生效的控制术1.定位my.cnf文件2.添加核心参数不重启热更新:高手应

在 PyQt 加载 UI 三种常见方法

《在PyQt加载UI三种常见方法》在PyQt中,加载UI文件通常指的是使用QtDesigner设计的.ui文件,并将其转换为Python代码,以便在PyQt应用程序中使用,这篇文章给大家介绍在... 目录方法一:使用 uic 模块动态加载 (不推荐用于大型项目)方法二:将 UI 文件编译为 python 模

如何将Python彻底卸载的三种方法

《如何将Python彻底卸载的三种方法》通常我们在一些软件的使用上有碰壁,第一反应就是卸载重装,所以有小伙伴就问我Python怎么卸载才能彻底卸载干净,今天这篇文章,小编就来教大家如何彻底卸载Pyth... 目录软件卸载①方法:②方法:③方法:清理相关文件夹软件卸载①方法:首先,在安装python时,下