Template

_Ink · 2023-11-30 20:42:13 · 个人记录

发现 OI 时期的模板整理好像不够用了，于是重新整理了一版。

整理这玩意的工作量比我想象的大...所以随缘更新整理吧

• 排序算法

  1、快速排序

  2、归并排序

  3、堆排序

  4、基数排序

• 字符串

  1、哈希与哈希表

  2、KMP

  • Problem & Code:

    ① P3375 【模板】KMP & Code

    ② P4391 [BOI2009] Radio Transmission 无线传输 & Code

    ③ P2375 [NOI2014] 动物园 & Code

  • Blog:

    ① KMP 详解好文

  3、Trie 字典树

  • Problem & Code:

    ① P8306 【模板】字典树 & Code

    ② P3879 [TJOI2010] 阅读理解 & Code

  4、AC 自动机

  • Problem & Code:

    ① P3808 【模板】AC 自动机（简单版） & Code

    ② P5357 【模板】AC 自动机（二次加强版） & Code

  5、manacher 算法

• 数据结构

  1、单调队列

  • Problem & Code:

    ① P1886 滑动窗口 /【模板】单调队列 & Code

    ② P2216 [HAOI2007] 理想的正方形 & Code

  2、ST 表

  • Problem & Code:

    ① P3865 【模板】ST 表 & Code

    ② P2216 [HAOI2007] 理想的正方形 & Code

  3、树状数组

  • Problem & Code:

    ① P3374 【模板】树状数组 1 & Code

    ② P3368 【模板】树状数组 2 & Code

  4、线段树

  • Problem & Code:

    ① P3372 【模板】线段树 1 & Code

    ② P3373 【模板】线段树 2 & Code

    ③ GSS3 - Can you answer these queries III & Code

    ④ CF1146E Hot is Cold & Code

  5、分块

  • Problem & Code:

    ① P3372 【模板】线段树 1 & Code

    ② P2801 教主的魔法 & Code

  6、莫队

  • Problem & Code:

    ① SP3267 DQUERY - D-query & Code

    ② P1903 [国家集训队] 数颜色 / 维护队列 & Code

  7、平衡树

  • Problem & Code:

    ① （Treap）P3369 【模板】普通平衡树 & Code

    ② Splay & Code

    ③ P3391 【模板】文艺平衡树 & Code

  8、主席树

  • Problem & Code:

    ① P3919 【模板】可持久化线段树 1（可持久化数组） & Code

    ② P3834 【模板】可持久化线段树 2 & Code

    ③ 区修区查主席树 & Code

  9、树套树

  • Problem & Code:

    ① P2617 Dynamic Rankings & Code

    ② 待补

• 图论

  1、建图与存图

  2、并查集

  • Problem & Code:

    ① P3367 【模板】并查集 & Code

  3、最小生成树

  • Problem & Code:

    ① P3366 【模板】最小生成树 & Code

    ② P1967 [NOIP2013 提高组] 货车运输 & Code

  4、最短路

  • Problem & Code:

    ① （Dijkstra）P4779 【模板】单源最短路径（标准版） & Code

    ② Bellman_Ford & Code

    ③ SPFA & Code

  5、差分约束

  • Problem & Code:

    ① P5960 【模板】差分约束 & Code

  6、负环

  • Problem & Code:

    ① P3385 【模板】负环 & Code

  7、拓扑排序

  • Problem & Code:

    ① B3644 【模板】拓扑排序 / 家谱树

    ② P1347 排序 & Code

    ③ P3243 [HNOI2015] 菜肴制作 & Code

  8、强连通分量与缩点

  • Problem & Code:

    ① P8435 【模板】边双连通分量 & Code

    ② P8435 【模板】点双连通分量

    ③ P3387 【模板】缩点 & Code

  9、割点与桥

  • Problem & Code:

    ① P3388 【模板】割点（割顶） & Code

    ② 桥 & Code

  10、欧拉回路

  11、二分图匹配

  • Problem & Code:

    ① P3386 【模板】二分图最大匹配 & Code

  12、2-SAT

  • Problem & Code:

    ① P4782 【模板】2-SAT & Code

• 树论

  1、树的直径与重心

  • Problem & Code:

    ① （树的重心）P1395 会议 & Code

  • Blog:

    ① 树的重心

  2、最近公共祖先（LCA）

  • Problem & Code:

    ① （倍增）P3379 【模板】最近公共祖先（LCA） & Code

    ② （重链剖分）LCA & Code

  3、树上差分

  • Problem & Code:

    ① （树上点差分）P3128 [USACO15DEC] Max Flow P & Code

  4、01 Trie

  • Problem & Code:

    ① P4551 最长异或路径 & Code

  5、笛卡尔树

  • Problem & Code:

    ① P5854 【模板】笛卡尔树 & Code

    ② P1377 [TJOI2011] 树的序 & Code

  6、树链剖分 / 重链剖分

  • Problem & Code:

    ① P3384 【模板】重链剖分/树链剖分 & Code

    ② GSS7 - Can you answer these queries VII & Code

  7、点分治

• 数论

  1、线性筛

  2、最大公约数（gcd）

  3、快速幂

  4、裴蜀定理

  5、扩展欧几里得（exgcd）

  6、乘法逆元

  7、矩阵加速

  8、组合数学基础

  9、中国剩余定理

• 动态规划

  1、背包九讲

  2、线性 dp

  3、区间 dp

  4、树形 dp

  5、状压 dp

  6、数位 dp

  7、动态规划的优化

• 其他

  1、离散化

  2、三分

  3、bitset 优化