“2024 年 7 月”
算法学习笔记16——网络流最大流
算法学习笔记(16):网络流最大流 网络 是一种特殊的带权有向图, 有以下几个特殊概念: 容量:边的权值,流在边上的最大量。 源点:没有入度的点 汇点:没有出度的点 流:每一条边都有对应的流量...
算法学习笔记15——状压DP
算法学习笔记(15):状压DP 状压DP也就是用到了状态压缩思想的动态规划。 状态压缩通常利用01位来对状态进行概括,位运算的效率高,能把看似N的状态直接变成1(前提是N不大) 动态规划都需要状...
算法学习笔记14——AC自动机
算法学习笔记(14):AC自动机 这名字听起来也太高级了,但实际上就是KMP+TIRE树。 所以不妨别管这个名字(Aho–Corasick Automaton) 实际上目的是多字符串匹配查找。 ...
算法学习笔记13——树上启发式合并
算法学习笔记(13):树上启发式合并 启发式算法是根据经验和直观感觉,对算法的优化,也就是指优化容易理解。 树上启发式合并看似高级,实际上是针对树上不带修改的离线子树问题的解决。 离线指的就是树...
算法学习笔记12——CDQ分治
算法学习笔记(12):CDQ分治 CDQ分治是一种思想,将复杂问题转化为简单问题。多维问题转为降维问题。 偏序问题 以一维二维三维偏序作为例子,可以体现CDQ分治的降维思想。 一维偏序 给n个数...
算法学习笔记11——容斥原理的简单应用
算法学习笔记(11): 容斥原理的简单应用 容斥原理 容斥原理本身易于理解,实际上是减去重复计算的部分的思想。 类似于两个有交集的集和并集,就是两个集合相加减去交集。 容斥模型概念 全集:各种...