RainAir
My OI Blog
RainAir


文章归档

初级的动态规划

感觉自己 dp 非常的差,于是在这里集中整理一下。 这里都是非常初级的动态规划。 定义 何为动态规划? 大概上就是一个不断探索问题性质减少那些和答案有关的值的个数。 动态规划重要的三部曲: 设计状态 考虑转移 考虑优化 由于这里是入门级别的动态规划,将…

   274   2018-07-30 去围观

主席树学习笔记

在学习主席树之前一定要先学会线段树 主席树定义 主要思想:主席树是利用函数式的编程思想使得线段树支持查询历史版本,同时充分的利用不同版本之间的共同版本来减少时间和空间复杂度的数据结构。一棵线段树的节点维护的是当前节点所对应的区间信息,若每次区间不同…

   200   2018-07-20 去围观

「NOIP2017」列队

题目链接 解题报告 我们对于每行建一棵线段树维护人,对于最后一列建一棵线段树。 我们要实现能插入删除的线段树,预先开点即可。 但是这样空间会爆,我们需要动态开点。 详情见代码。 [crayon-5ce6969b3771d241965046/]

   162   2018-07-17 去围观

贪心算法初步

定义 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后…

   158   2018-07-16 去围观

次小生成树

题目链接 题目描述 给定一张图,求出它的严格次小生成树。 解题报告 预备知识:最小生成树,最近公共祖先 我们首先来考虑一下严格最小生成树和不严格次小生成树的区别。 首先,对于一个图,可能不只有一个最小生成树。 那么,不严格次小生成树,只需要找出不…

   257   2018-07-13 去围观

「HAOI2015」树上操作

题目链接 这一道题的题解在luogu上的链接 解题报告 这一题是树链剖分的板子题。 什么?你不会树链剖分?点这里学习 对于操作1:直接在点的dfn在线段树的位置修改即可。 对于操作2:我们考虑在记录每个以该点为根的子树大小时,由于dfn的顺序一定是子树的dfn小…

   198   2018-07-12 去围观

「优化」内存池

实现 在c++中,我们非常喜欢使用指针。因为指针非常适合人们的思考方式。 所以我们来优化一下指针的速度。 你们想一下:嵌套7,8层数组和一些平等无嵌套的箭头,哪个更容易理解? ~~当然是前者啦~~ 指针非常亲和人们的语言和思维习惯,所以被众多OIer所追求。 …

   324   2018-07-12 去围观

多次询问的最长瓶颈路

题目链接 题目大意 给出一个由 $ n $个点 $ m $条边的图,现有$ q $组询问,每次需要你求出从$ x $到$ y $的一条简单路径,使路径上所有边中最小值最大,并输出这个最大值。 若不存在这样的路径,则输出$ −1 $。 解题报告 做这一道题之前,建议先看一下单次询问…

   200   2018-07-10 去围观

单次询问的最长瓶颈路

题目链接 题目大意 给定一个图,求瓶颈最短路(及求出一条是该路径最大值最小的路径)。 解题报告 方法一 注意最大值最小,我们立马想到了二分。 实际上,由于这道题拥挤度的范围不大,可以二分。 二分的区间就在边权最小值与最大值之间。 我们使用bfs来检查…

   214   2018-07-08 去围观

SA算法学习笔记

最近闲的无聊,学了一个模拟退火算法... 定义 首先,我们来了解一下这些算法的来历和用处。 人们在做一些复杂度为指数级别的题目时,忍受不住这种高复杂度的方法,于是发明了各种随机算法来获得近似最优解,例如爬山算法,模拟退火,遗传算法和蚁群算法等。 那么…

   152   2018-07-08 去围观
加载更多
文章归档