动态规划(DP)学习笔记
动态规划(Dynamic Programming)本质上是图论问题。数位 DP按照数字的位数划分转移阶段转移方式:枚举下一位数字填什么限制条件:数位的上下界要求[1, r] 区间数字个数[l, ...
动态规划(Dynamic Programming)本质上是图论问题。数位 DP按照数字的位数划分转移阶段转移方式:枚举下一位数字填什么限制条件:数位的上下界要求[1, r] 区间数字个数[l, ...
bitset 可以用来进行一些玄学优化,所以又被称为骗分神器。还能用来卡常
总是忘记读入优化的板子,在这里 Mark 一下。
前面这篇文章着重介绍了 Tarjan 算法找强连通分量的方法。此文章着重介绍缩点。寻找 SCC 的方法依然是 Tarjan 算法。
强连通与强连通分量(SCC)首先需要知道它们的定义……强连通:有向图中两个点可以相互到达,那么它们就是强连通的。强连通分量:有向图中的一组点可以相互到达(就是多个点可以相互到达)缩点:把强连通分...
关于 SPFA,它死了。以前的最短路算法一直都用的 SPFA,说到原因,那就是兼容性和速度都比较好(而且好写),毕竟 Dijkstra 不能处理存在负环的情况。
启发式搜索是利用问题自身特性信息(启发信息)来引导搜索过程,达到减少搜索范围,降低问题复杂度的搜索方法。
set 是 C++ STL 中关于集合的库,和数学上的集合一样,元素具有唯一性,默认对元素从小到大进行排列。注:multiset 中集合元素可以重复
线段树是一种很实用的数据结构,所以也要学习一下。线段树是用来处理区间问题的,复杂度能到达 $O(\log n)$。就以洛谷的模板题 线段树 1 为例吧。
manacher 算法是用来求最长回文串长度的算法,复杂度是线性的($O(n)$)基本思想是枚举以每一个点为中心,找出可以扩展的最长长度(用 r[i] 表示),然而会出现长度为偶数的情况无法枚举...