1 淼润淽涵

尚未进行身份认证

暂无相关简介

等级
TA的排名 3w+

51nod 1102 面积最大的矩形(单调栈)

ProblemDescription有一个正整数的数组,化为直方图,求此直方图包含的最大矩形面积。例如2,1,5,6,2,3,对应的直方图如下:面积最大的矩形为5,6组成的宽度为2的矩形,面积为10。输入第1行:1个数N,表示数组的长度(0<=N<=50000)第2-N+1行:数组元素A[i]。(1<=A[i]<=...

2019-10-20 16:08:06

学习总结

最近两天没有学很多新东西,因为主要看的是处理字符串的各种算法。因为它们的相对题型很固定,翻来覆去就那几种,顶多和二分以及哈希联系一下,所以变化较少较简单。做的51nod上的题目,前面很简单,按AC数量做的,后面的大概模块我看了一下,也就是哪几种,但题目还没有具体做。突然今天看到一个还有个可持久化线段树的专项,我还没有系统看,回来最近得把它学了。其实我感觉51nod上的题目只是一个辅助,关键还是...

2019-10-17 00:41:33

BZOJ 1036 树的统计(线段树+树链剖分)

Description一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作:I.CHANGEut:把结点u的权值改为tII.QMAXuv:询问从点u到点v的路径上的节点的最大权值III.QSUMuv:询问从点u到点v的路径上的节点的权值和注意:从点u到点v的路径上的节点包括u和v本身Input输...

2019-10-16 22:11:11

有序的双链表的实现

描述定义有序的双链表类,链表中存储整型数据,创建带头结点的有序双链表,要求包含以下成员函数:双链表的构造函数(非空的链表,输入数据为0,表示输入结束)插入操作(将一个数据元素插入到有序的双链表中,插入之后链表仍然有序,输入数据为0表示插入操作结束)按值删除节点(考虑有重复值的情况)双链表的遍历操作双链表的析构输入输入链表中的元素,根据输入元素,创建有序双链表...

2019-10-14 21:28:46

单链表的实现

描述定义单链表类,创建带头结点的单链表(节点类型为整型数据),要求包含以下成员函数:头插法创建单链表(利用构造函数实现)尾插法创建单链表(重载构造函数实现)链表的遍历按值删除一个节点按位置删除一个节点链表的析构输入输入一组数据,以尾插法的形式创建单链表(0表示输入结束)(构造第一个链表)输入一组数据,以头插法的形式创建单链表(0表示输入结束)(构造第二个链表...

2019-10-14 21:07:00

学习总结

这两天,一个是学习了主席树的两种,一种是静态的主席树的查询(对于每次查询,输出区间[l,r]中第k大的数),还有是一种动态的主席树的查询(可以随时进行单点或区间的修改并随时输出区间[l,r]中第k大的数)。因为前两天学习的树链剖分,所以这两天就紧接着学的LCA,像和线段树优化结合,以及树链剖分,以及离线tarjan算法(图论的),还有和深搜一遍整棵树在回溯的时候利用树形dp结合的(这个看的还不...

2019-10-13 23:49:57

学习总结

这两天学习了树链剖分和线段树结合起来的维护以及修改树上路径的问题。其实看明白了就是先树链剖分用两个dfs序将树上路径转化为线段树的区间,然后就还是线段树单点以及区间修改查询的那一套,这也算是一种类型的题木吧。树链剖分的作用就是将一棵树变成一个可处理的dfs序,对于树上操作一般都是由线段树和树状数组维护。另外,还学习了dfs序和欧拉序的不同以及应用。用dfs序求出每个节点的入时间戳以及出时间戳,...

2019-10-10 00:05:26

DFS序与欧拉序的区别

DFS序与欧拉序的区别dfs序:是指将一棵树被dfs时所经过的节点顺序(不绕回原点)。欧拉序:就是从根结点出发,按dfs的顺序在绕回原点所经过所有点的顺序。作用通过dfs序判断v节点的时间区间是否在u节点的时间区间内。通过欧拉序求u和v的最近公共祖先。用图说话dfs序:A-B-D-E-G-C-F-H欧拉序:A-B-D-D-E-G-G-E-B-C-F-H-H-F-...

2019-10-08 21:11:55

学习总结

这两天学了一些关于涉及到将树用dfs序和邻接数组(链式前向星)转化为线性的线段树以及好用的树状数组的所处理的单点修改,区间修改以及区间查询等问题,并带出来了LCA最近公共祖先都可以实现。另外今天又捎带着看了一点欧拉序以及欧拉序的用途Tarjan算法(离线算法)即:首先读入所有的询问(求一次LCA叫做一次询问),然后重新组织查询处理顺序以便得到更高效的处理方法。Tarjan算法是一个常见的用于解...

2019-10-07 02:17:06

Apple Tree(树状数组+dfs序+邻接表数组(链式前向星) )

链接:http://poj.org/problem?id=3321DescriptionThereisanappletreeoutsideofkaka'shouse.Everyautumn,alotofappleswillgrowinthetree.Kakalikesappleverymuch,sohehasbeencareful...

2019-10-07 01:45:29

链式前向星

如果说邻接表是不好写但效率好,邻接矩阵是好写但效率低的话,前向星就是一个相对中庸的数据结构。前向星固然好写,但效率并不高。而在优化为链式前向星后,效率也得到了较大的提升。虽然说,世界上对链式前向星的使用并不是很广泛,但在不愿意写复杂的邻接表的情况下,链式前向星也是一个很优秀的数据结构。...

2019-10-06 19:55:59

二叉树的前序、中序、后序遍历

一棵二叉树由根结点、左子树和右子树三部分组成,若规定D、L、R分别代表遍历根结点、遍历左子树、遍历右子树,则二叉树规定为3种遍历方式:DLR--前序遍历(根在前,从左往右,一棵树的根永远在左子树前面,左子树又永远在右子树前面)LDR--中序遍历(根在中,从左往右,一棵树的左子树永远在根前面,根永远在右子树前面)LRD--后序遍历(根在后,从左往右,一棵树的左子树永远在右子树...

2019-10-06 18:23:33

树状数组

对于一个n元素的数组A[n],可执行如下操作(单点修改,区间查询):Add(I,d):让A[i]变成A[i]+d。Query(L,R):返回A[L]+A[L+1]+…+A[R]。注意:树状数组只能计算A[1]开始的和,A[0]这个元素是不能用的。上面单点修改和区间查询操作复杂度都是O(logn)。其实树状数组还可以处理区间更新,单点查询的问题。如HDU155...

2019-10-05 10:50:50

学习总结

这两天主要看了线段树集中几种类型的题目。第一道是因为如果不离散化要开10的八次方的数组。而在,线段树中开这么大会超时。一般见的都是开到10的5次方的数量级。第二个是一道铁路的关于转化为线段树的题目。问题是转化成对n-1个数进行m次区间更新最值,对于每段铁路而言,min表示该最早被使用的时间,max表示最后一次被使用的时间,最小花费即区间查询就是每天都加上这段铁路的花费,更新用线段树upda...

2019-10-02 22:01:31

学习总结

近两天主要看的线段树方面的题目。然后发现用到线段树的题目虽然有各种类型,但追其根本都是为了降低时间复杂度,两种本质:一种是单点修改区间查询,另一种是区间修改区间查询操作。只要题目的本质涉及到这两种操作,都可以是用线段树来解决。其实难点主要是考虑线段树每个节点维护什么信息,还有如何通过线段树维护的节点信息来解决题目所要求的问题。从而修改写出build,pushup,update,query四个函数来...

2019-09-29 23:18:44

线段树

线段树单点add,区间sum查询的模板#include<cstdio>#include<cstring>usingnamespacestd;constintmaxn=50000+5;//线段树需要维护的信息intsum[maxn*4];#definelsoni*2,l,m#definersoni*2+1,m+1,r...

2019-09-29 17:26:28

9月25日学习总结

前两天把RMQ算法的那几道题目收尾了以后,今天又开始看的后缀数组的算法,看了道给你一个字符串,要你求出这个串中的最长回文字串,如果存在多个,则输出第一次出现的那个的题目,这道题目其实用马拉车算法实现更简单,上一次打比赛时就涉及到求最长回文子串用马拉车算法的。所以又复习了一遍马拉车算法。然后又看了几道用后缀数组求公共子串和最长公共子串的题目,都是些标准的后缀数组的题目。明天还要接着看把后缀数组和...

2019-09-25 22:18:05

RMQ算法

RMQ算法可以解决对于一个整数数组(也可以是其他可比较大小的元素类型)的任意区间[L,R]查询最值问题。RMQ能在经过O(nlogn)的时间预处理后,做到O(1)时间复杂度的任意区间最大最小值查询。RMQ算法模板RMQ问题的简单应用。即给你一个数组,要你输出每次询问区间内的最大值-最小值的差。#include<cstdio>#...

2019-09-23 18:38:44

学习总结

最近主要看了RMQ算法的相关题目。这两天杂事比较多,所以看得进度比较慢。幸亏下周就没什么杂事啦,可以多学很多。RMQ问题可以解决对于一个整数数组(也可以是其他可比较大小的元素类型)的任意区间[L,R]查询最值时,能在经过O(nlogn)的时间预处理后,做到O(1)时间复杂度的任意区间最大最小值查询。接下来大概写一下几种题目:题目:给出一个非降序排列的整数数组a1,a2,...an,你的任...

2019-09-23 00:28:57

数据结构之线性表

线性表基本操作模板constintMaxSize=100;template<classDataType>classSeqList{public: SeqList(){length=0;}//无参构造函数,建立一个空的顺序表 SeqList(DataTypea[],intn);//有参构造函数,建立一个长度为n...

2019-09-22 23:28:01

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周上午根据用户上周周三的博文发布情况由系统自动颁发。