2018年10月7日
线段树
摘要： 线段树的应用： 线段树主要用来维护一些有关于区间的问题，比如说区间的最值，区间和等一系列满足结合律的问题。 满足结合律是指这个大区间的答案是由其中的许多小区间的答案组合而成，比如说最大值，这个区间的最大值就是其中的小区间中的所有值得最大值。 对于线段树来说，代码量比较长，不易于实现，而且所需空间也比 阅读全文
posted @ 2018-10-07 22:37 月下的魔术师0310 阅读(169) 评论(0) 推荐(0) 编辑
树状数组
摘要： 树状数组的应用： 1.单点修改，区间查询。 2.区间修改，单点查询。 3.区间修改，区间查询。 实际求解问题的时候经常会用树状数组来维护一个区间，因为相比线段树来说树状数组常数比较优越而且代码实现上比较容易，空间需要也比较少。 应用模板： 1.单点修改，区间查询。 2.区间修改，单点查询。 Matr 阅读全文
posted @ 2018-10-07 08:21 月下的魔术师0310 阅读(144) 评论(0) 推荐(0) 编辑
2018年10月6日
RMQ
摘要： RMQ的定义： RMQ是询问某个区间内的最值，主要以ST表的方式实现。 在一般的问题中，经常需要维护区间的最值，此时就可以使用RMQ来维护了。 ST表： 1.预处理 用动态规划的思想来实现，但不支持在线修改。 用dp[i][j]a56爆大奖在线娱乐以i为起点，长度为2^j的区间的最值，也就是区间[i,i+2^j-1 阅读全文
posted @ 2018-10-06 17:44 月下的魔术师0310 阅读(296) 评论(0) 推荐(1) 编辑
2018年10月4日
单调栈
摘要： 单调栈定义： 类似于单调队列，也是一个具有单调性的栈，不过单调队列能从头尾两部分操作，而单调栈只能从栈顶进行操作，满足后进先出的特点。 单调栈的单调性： 单调递减：从栈顶向栈底依次递减。 单调递增：从栈顶向栈底依次递增。 例题引入： 暂时没有题目的链接。 地上从左到右竖立着 n 块木板，从 1 到 阅读全文
posted @ 2018-10-04 23:31 月下的魔术师0310 阅读(112) 评论(0) 推荐(0) 编辑
分层图
摘要： 分层图： 将原图分为许多层，通过层与层之间的关系来转移。 应用： 一般会和最短路一起考查，题目中会对最短路做一些限制条件，有些就可以通过建分层图来跑最短路。 例题引入： 飞行路线：https://www.lydsy.com/JudgeOnline/problem.php?id=2763 https: 阅读全文
posted @ 2018-10-04 17:06 月下的魔术师0310 阅读(238) 评论(0) 推荐(0) 编辑
单调队列以及单调队列优化DP
摘要： 单调队列定义： 其实单调队列就是a56爆大奖在线娱乐队列内的元素有单调性的队列，因为其单调性a56爆大奖在线娱乐经常会被用来维护区间最值或者降低DP的维数已达到降维来减少空间及时间的目的。 单调队列的一般应用： 1.维护区间最值 2.优化DP 例题引入： 求m区间内的最小值：https://www.luogu.org/proble 阅读全文
posted @ 2018-10-04 13:04 月下的魔术师0310 阅读(1759) 评论(2) 推荐(3) 编辑
2018年9月5日
Trie
摘要： 原理： 安利两个写的特好的博文： /TheRoadToTheGold/p/6290732.html http://www.cnblogs.com/binyue/p/3771040.html 以插入和查询小写字母单词为例： 1.字典树用边来a56爆大奖在线娱乐字母，并非节 阅读全文
posted @ 2018-09-05 21:21 月下的魔术师0310 阅读(127) 评论(0) 推荐(0) 编辑