Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 上下界网络流学习笔记

    在普通的网络流问题中,给定单一的源点与汇点,每条边有流量上界(容量),在其它所有点满足流量平衡条件,且流出 s s 的流量等于流入 t t 的流量的前提下,求 s s t t 的最大流。而有一类网络流问题,每条边不仅有流量上界,还有流量下界,这类问题需要转化求解。

    于  OI, 学习笔记, 算法模板, 网络流 继续阅读

  2. 计算几何学习笔记

    计算几何(Computational Geometry),是一系列使用计算机解决几何问题的算法。与解析几何相比,计算几何更适合计算机运算,精度较高,运算速度较快,并且易于编写。

    本文只包含二维计算几何在 OI 中的部分应用。

    于  学习笔记, 数学, 算法模板, 计算几何 继续阅读

  3. Manacher 学习笔记

    Manacher 可在 O(n) O(n) 的时间内求出一个字符串以每个位置为中心的最长回文子串。

    于  Manacher, 字符串, 学习笔记, 算法模板 继续阅读

  4. 欧拉回路学习笔记

    若图 G G 中存在这样一个环,使得 G G 中每条边都恰好在环上出现一次,则称为欧拉回路。

    具有欧拉回路的图称为欧拉图。

    于  图论, 学习笔记, 欧拉回路, 算法模板 继续阅读

  5. Tarjan 点双连通分量学习笔记

    点双连通分量是一个极大的子图,满足图中删去任何一个点都不会改变图的连通性。

    于  Tarjan, 双连通分量, 图论, 学习笔记, 算法模板 继续阅读

  6. RMQ 模板

    RMQ 稀疏表(Sparse Table)的模板。

    zyz 大佬的评价

    于  RMQ, 数据结构, 算法模板 继续阅读

  7. AC 自动机学习笔记

    AC 自动机是一种多模式串匹配算法,可以用来在文本串中匹配一系列模式串,其时间复杂度与串的总长度成正比。

    于  AC 自动机, 字符串, 学习笔记, 算法模板 继续阅读

  8. Tarjan 割点学习笔记

    在一个无向图中,如果删掉点 v v 后图的连通块数量增加,则称点 v v 为图的割点

    于  Tarjan, 割点, 图论, 学习笔记, 算法模板 继续阅读

  9. 从傅里叶变换到数论变换

    FFT 可以用来计算多项式乘法,但复数的运算会产生浮点误差。对于只有整数参与的多项式运算,有时,使用数论变换(Number-Theoretic Transform)会是更好的选择。

    于  原根, 多项式, 学习笔记, 数学, 数论, 算法模板 继续阅读

  10. 点分治学习笔记

    点分治是用来解决树上路径问题的一种方法。

    于  学习笔记, 数据结构, 点分治, 算法模板 继续阅读