分类: 算法

21 篇文章

【整理】算法竞赛字符科技学习笔记
KMP KMP 是一种用于两个字符串匹配的算法。其核心概念是 Border ,即一个字符串同长度的完全相同的前后缀(通常不含自身)。 KMP 的做法是先求出要匹配的字符串(短串)的所有前缀的最长 Border,然后在于长串进行匹配,并在无法匹配时跳转到其 Border 进行再次尝试匹配。详细方法可以参考我之前的学习笔记。 有时也会用 $next_i…
【整理】算法竞赛动态规划学习笔记
一些动态规划类型 树形 DP 树形 dp 的常用方法(例如树上背包)是将接下来要处理的儿子与以及处理完的儿子的全体进行合并,即把处理多个子树的问题转换为依次合并两个儿子的问题。 树形 dp 类型众多,故这里不多做赘述。 状压 DP 状压 dp 的核心是把状态用二进制数进行压缩(有些时候可能会用到四进制,如果一个点有三种或四种状态)。处理状压 dp …
【整理】算法竞赛计算几何学习笔记
二维基础 特殊值与精度 无穷 $1.0/0.0=\operatorname{INFINITY},1.0/0.0=\operatorname{-INFINITY}$ 非数 $0.0/0.0 =\operatorname{NAN}$ 要注意,$\operatorname{NAN} (\ge,\le,>,<,= ) x$ 结果均为 False,只有…
【整理】算法竞赛数学相关学习笔记
这个笔记想写得稍微详细一点,部分内容来自我自己之前的博客: OI 里的数学内容整理(提高组)。 其中一些公式是 AI 从 PPT 上识别的,格式混乱,还请谅解。 整数分解与筛法 欧几里得算法 用于求解两个数的最大公因数。 $\gcd(a,b)=\gcd(b,a\bmod b)$。 int gcd(int a,int b){ return b==0?…
【整理】算法竞赛图论进阶学习笔记
图匹配 二分图匹配 判定 静态:黑白染色。 动态:分层并查集。并查集可以维护的可以是点的连接关系,也可以是关系的连接方式。连接两个点,我们可以改为连接这两个点的逻辑关系,黑-白,白-黑。如果有一天同一个点的黑白被连在了一起,则这就不是一个二分图。 分层并查集经典例题:P2024 [NOI2001] 食物链。 最大匹配:匈牙利算法 模版:P3386 …
【整理】算法竞赛数据结构学习笔记
区间信息维护 前缀和与差分 多维前缀和 多维前缀和可以通过一维一维处理的方式,将复杂度控制在可控范围。 例如二维前缀和求法: $sum_{i,j}=a_{i,j}$ $sum_{i,j}+=sum_{i-1,j}$ $sum_{i,j}+=sum_{i,j-1}$ 例题:NC225630 智乃酱的子集与超集。 数列上加多项式 给一个数列的一部分连续…
fhq_treap(无旋 treap) 学习笔记
fhq_treap(无旋 treap) 参考:远航之曲的博客。 感觉比较意识流。 核心思想是平衡树分裂和合并。 类似于 Splay 把区间分离出来,fhq_treap 可以把平衡树进行分裂来提取需要的区间,再通过合并平衡树来维持树高(即堆性质)。这样不仅可以做到维护区间,还免去了旋转操作,代码较为简单。 split & merge &…
最小费用最大流(MCMF)简要学习笔记
在打 P3705 [SDOI2017]新生舞会 时发现原代码似乎出了点问题。现在不推荐本博客的写法,更推荐类似于 Dinic 的 spfa+dfs 的写法,详见最下方的“附加代码”部分。 MCMF(基于 spfa 实现) 模板题:Luogu3381。 即给定一张网络,每条边都有一个权值和流量限度,这条边上每有一个流量,总费用就加上这个权值,你需要在…
块状链表学习笔记
块状链表 参考:Tak_vin 的 博客 及相关代码。 这篇可能写的巨草,主要是给我自己看的。 一种根号数据结构,支持一个区间的动态插入和随时访问。 以 Luogu4008 [NOI2003] 文本编辑器 为例。 题意: 维护一个文本编辑器,支持: Move/Prev/Next 移动光标位置 Insert 在光标处插入若干个字符 Delete 删除…
树上启发式合并(dsu on tree)学习笔记
参考:p_z_y 的博客,YellowBean 的代码启示。 尽量写短点。 dsu on tree 模板题:CF600E Lomsat gelral。 题意: 有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。 每个结点都有一个颜色,颜色是以编号表示的, $i$ 号结点的颜色编号为 $c_i$。 如果一种颜色在以 $x$ 为根的子树内出现次数…