2 默归

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 41w+

RMQ问题:高效离线算法——ST

ST算法的实现ST算法是一种解决静态询问区间最值问题的高效离线算法,算法上采用了倍增的思想,而实现上则是利用了动态规划,具体流程如下所示:对于区间[begin , end],将其拆分为两个区间:[begin , begin+]、[end-, end],,每个区间的长度为。然后继续拆分这两个区间,此时区间的长度为,此后每次拆分都将区间缩短一半(x-1),不断拆分直到区间长度为1(即x=0)...

2020-03-10 11:25:57

基本数据结构:二叉堆

导入我们在解决问题时经常会遇到需要不断维护一段数据内最值的情况,用更精确的话来说就是:存在集合S,里面的元素可能会随时增加、删除、修改,而我们需要做到随时返回集合内的最值,如果采用遍历的方式维护最值,则每次维护都将遍历所有数据,其效率往往十分低下。为解决这个问题,我们就引入了一个新的数据结构——二叉堆。二叉堆二叉堆实际上是一种特殊的二叉树,它在普通的二叉树基础上添加了以下条件:1...

2020-03-07 18:16:03

基本数据结构:并查集

导入并(union)查(find)集(set),是一种根据功能来命名的数据结构。从它的名字中我们就能知道,它的主要功能有:1.union:合并两个集合(编写程序时应注意,union在c语言中为关键字,代表联合体,无法作函数名称)2.find:查找某个元素所在的集合也就是说,并查集是一种用来处理集合关系的数据结构。所以对于之前我们处理起来很麻烦的集合问题,在引入并查集之后就会变...

2020-01-30 22:59:18

基本数据结构:队列(单调队列、优先队列)

队列的思想队列是一种先进先出的线性表,只允许在队头进行删除操作,在队尾进行插入操作。先进先出的顺序符合我们日程生活中的事件调度过程,例如排队等等。队列就非常适合模拟这些过程,它的结构示意图如下: 值得注意的是,在前面的元素出队以后其占用的空间就不再被利用,造成了浪费,于是我们在队列存储到允许的最大空间时(但其实这时队列并未真正存满),继续添加的元...

2020-01-26 17:12:29

根号算法:莫队算法

导入 莫队算法,也算是一个黑科技算法,能切掉好多区间题啊,和分块一样属于一个ACMer/IOer必备的算法,而由于莫队算法里面用到了一点点分块的内容,所以先弄懂分块还是有必要的。同时由于和分块扯上了关系,那么它的时间复杂度也就自然而然地是根号级别的了,能解决的数据规模还是挺大的。ok,那么莫队算法到底是什么呢,下面就来介绍这个黑科技算法。 普通莫队 先来直接看看莫队的思想:莫队算...

2019-12-03 09:13:15

根号算法:分块

导入 众所周知,我们熟悉的算法时间复杂度有常数级,对数级、线性级、次方级、指数级等等,其中为应对题目规模对时间复杂度的要求,我们一般要将算法的时间复杂度优化到对数级,但是实际上我们还有一种优化方法——根号算法,它的时间复杂度为级,同样可以应对大部分的题目规模,并且具有相当大的可拓展性。和对数算法基本对应分治类似,根号算法也对应着一种操作,就是本篇博客要介绍的分块。 什么是分块? ...

2019-10-14 01:06:48

高级数据结构:线段树(Lazy标记的两种处理方法)

目录 线段树的使用 1.线段树的建立 2.区间询问 3.单点修改 4.区间修改 例题及其补充

2019-08-06 18:41:32

基本数据结构:栈(单调栈)

目录 栈的思想 栈的应用1.模拟栈操作2.括号匹配问题3.表达式求值 单调栈 例题及补充栈的思想栈是一种后进先出(LIFO)的线性表,只允许在栈顶进行插入删除操作。后进先出是栈最基本的特征,有点类似于向一个桶中放东西,你最先能拿出的只能是你最后放下去的东西,而想要继续拿下层的东西,你就不得不先把上层的东西全...

2019-09-13 16:09:55

高级数据结构:树状数组(区间修改、逆序对问题)

目录 前缀和与差分数组 1.前缀和数组 2.差分数组 树状数组的使用 1.树状数组的建立 2.区间询问 3.单点修改 4.与差分数组结合后实现区间...

2019-08-06 18:39:59

巧解回文串:Manacher算法

引入 什么是回文串想必不用解释了吧,相信大家应该都做过判断一个字符串是否是回文串的题,而解题思路也很简单:依次匹配第一位与最后一位字符,第二位与倒数第二位字符...直到匹配完整个串为止(也可以从中间向两边判定,且这样与Manacher算法更加接近)。那么,将题目改成判断一个字符串是否含有回文子串,该如何解决?改成求出字符串中最长回文子串的长度,又该如何解决呢?其实能够解决的算法有很多,这里...

2019-09-03 23:19:43

浅析数位DP

目录数位dp的模板数位dp的思想数位dp的例题模板:话不多说,直接上模板,刚开始实在搞不懂的话也没问题,会套模板就行(手动滑稽):typedef long long ll;int temp[pos];ll dp[pos][sta]//如果需要处理前导零,还需加入一个参数bool lead判断是否为前导零ll dfs ( int pos , int sta ,...

2019-08-04 00:56:20
勋章 我的勋章
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。