Main Navigation 首页算法模板知识点竞赛题解

Appearance

Sidebar Navigation

算法模板

总览

分专题模板总览

基础

总览

归并排序

前缀和

三维前缀和

二分

实数二分

三分

搜索

总览

双端队列

迭代加深

双向DFS

IDA*

双向广搜

A*

K短路

动态规划dp

总览

棋盘式状压dp

集合式状压dp

区间dp

二维区间dp

树形dp

树形背包

树形背包 $ O(N \sqrt N ) $

换根dp

数位dp

斜率优化dp

背包dp

概率期望dp

字符串

总览

字符串结论

字符串哈希

二维哈希

KMP

失配树

Z函数

Manacher

字典树

01-TRIE树合并

AC自动机

AC自动机与拓扑优化(求出现次数)

后缀数组

后缀自动机

回文自动机

回文自动机求双倍回文

判断分割两个回文串

Lyndon分解

最小表示法

字符串结论

数学

总览

博弈论

巴什博弈

Nim博弈

Nim-k游戏

阶梯nim博弈

anti-nim(反nim游戏)

威佐夫博弈

拓展威佐夫博弈

斐波那契博弈

莫比乌斯函数

莫比乌斯反演

一般使用式子

P2522 [HAOI2011] Problem b

试除法判断质数 $ O(\sqrt{N}) $

试除法分解质因数 $ O(logN) -O(\sqrt{N}) $

埃氏筛筛质数 $ O (N\sqrt{N}) $

质数筛 $ O(N) $

试除法求所有约数 $ O(\sqrt{N}) $

约数个数和约数之和

欧几里得求GCD $ O(logN) $

求欧拉函数 $ O(\sqrt{N}) $

筛法求欧拉函数

莫比乌斯函数筛

区间筛思想

Miller-Rabin素数判断

Pollard-Rho获取质因子

原根

类欧几里得

拓展欧几里得

组合数

中国剩余定理

拓展中国剩余定理

Burnside定理

Polya定理

生成函数

min-max容斥

矩阵快速幂

FFT

高精度乘法

NTT

任意模数NTT(MTT)

三模数NTT

FWT

FWT求三个集合异或的不同个数

FWT子集卷积

子集卷积(多个数有序)

子集卷积exp(多个数无序)

多项式板子

拉格朗日插值

重心拉格朗日插值法

多项式乘法逆

多项式求导

多项式求积分

多项式除法

多项式开根(a0=1)

多项式开根a0!=1

多项式对数函数（多项式 ln）

多项式指数函数（多项式 exp）

多项式多点求值

多项式快速幂

BSGS(Baby Step Grant Step)

exBSGS

欧拉定理

位进制

快速幂

高精加

高精减

高精乘低精

高精除低精

分数四则运算

高斯消元

高斯消元求行列式

Meiseel Lehmer算法(版本一)

Meiseel Lehmer算法(版本二)

二次剩余

裴蜀定理

快速幂模指数

类欧几里得推导

万能欧几里得

拓展欧拉定理

莫比乌斯反演

杜教筛

LUCAS定理

离散对数

Stern–Brocot 树与 Farey 序列

组合数学

特征根法求递推式

BSGS例题：随机数生成器

容斥原理

光速幂

数据结构

总览

对顶堆维护中位数

并查集

可撤销并查集

可撤销并查集与分治应用

分块

ST表

树状数组

线段树

线段树动态开点

线段树分治

李超线段树

线段树(历史最值+区间加+区间取min+求和+求目前最值)

线段树( 区间取max+维护异或和)

扫描线

Treap

FHQ-Treap按值分裂

FHQ-Treap按排名分裂

FHQ-Treap文艺平衡树实现区间翻转

可持久化平衡树

可持久化文艺平衡树

splay文艺平衡树实现区间翻转

Splay平衡树模板

动态树LCT

LCT维护边双连通分量

LCT维护子树信息

线段树套平衡树( $ n(log^2n+log^3n) $ )

可持久化线段树

线段树上二分

可持久化trie树

P3377 【模板】左偏树/可并堆

莫队

P1903 [国家集训队] 数颜色 / 维护队列(带修莫队)

歴史の研究(回滚莫队)

SP10707树上计数2(树上莫队板子)

P4887 【模板】莫队二次离线（第十四分块(前体)）

点分治

点分树

点分树模板

笛卡尔树

笛卡尔树分治(启发式分裂)

树哈希

Sqrt Tree

分块

树上带修莫队

树上莫队

回滚莫队

带修莫队

普通莫队

莫队+bitset

查询区间两个数$+,-,*,/$等于x

树分块

线段树合并

线段树分裂(指针版)

线段树维护前缀最大值(单调递增栈)

可删堆

分块套树状数组维护二维带修

操作序列分块

矩阵乘法模板类

区间历史版本和板子

区间历史版本和(矩阵板子)

无根树同构

图论

总览

删边最短路

CF1163F Indecisive Taxi Fee

树上问题

LCA

tarjan离线求LCA

树链剖分HLD

树链剖分之重链剖分

树链剖分之长链剖分

树上启发式合并

拓扑排序

最小生成树

prim算法

kruskal算法

kruskal重构树

boruvka算法求最小生成树

斯坦纳树

最短路

dijkstra $ O(n^2) $

堆优化的dijk

SPFA

spfa判负环

johnson算法求带负权边的全源最短路

传递闭包(floyd)

最小环

k短路 $ O(n^3logk) $

差分约束

tarjan求强连通分量

kosaraju算法(两次dfs求强连通分量)

tarjan求点双连通分量

tarjan求边双连通分量

动态维护边双连通分量

2-sat

2sat输出方案(n^2)

环计数问题

欧拉回路

【模板】欧拉路径(有向图输出字典序最小)

染色法判断二分图

匈牙利算法求解二分图

二分图最大权匹配（MaxAssignment 基于KM）

Hopcroft-karp 算法

一般图最大匹配

计算几何

总览

基础知识

凸包

极角排序

平面最近点对

平面最近最远点对随机法

旋转卡壳求凸包直径

旋转卡壳求最小矩形覆盖

k远点对

半平面交(求凸多边形的交集)

最小覆盖圆

三维计算几何基础

三维凸包

三角形面积并

最小圆覆盖

自适应辛普森积分

自适应辛普森积分求圆的面积并

计算积分(发散收敛)

杂项

总览

离散化

悬线法

最大子矩阵模型

障碍物法求解最大子矩阵

置换环

pb_ds库

引入

哈希表

平衡树

操作方法

普通平衡树板子

堆

rope(实际为可持久化平衡树，实现块状链表)

曼哈顿距离与切比雪夫距离

异或哈希

CDQ分治

cdq分治离线求解二维数点问题

普通二维数点问题

动态逆序对

bitset求解高维偏序

bitset优化传递闭包

bitset优化01矩阵乘法

bitset求解字符串匹配

color-coding算法

线性基

前缀线性基

区间线性基(单点修改，区间查询)($On\log n\log^2V$)

区间线性基(单点*插入*，区间查询，猫树分治法，前缀线性基)($O(n\log n \log V +m \log^2V)$)

区间线性基(区间异或，区间查询)

区间线性基(zak随机法)

二进制结论

01trie实现平衡树功能(32倍空间换时间)

替罪羊树

珂朵莉树

质数约数表

染色问题(思维)

KD-Tree

矩阵快速幂

求斐波那契数列

矩阵快速幂求解经过n条边的最短路

格雷码

dilworth定理

wqs二分

取模结论

总览

差同减差

和同加和

余同取余

本页目录

发布时间：2024-07-31

最短路

最后更新:

Pager

Previous page斯坦纳树

Next pagedijkstra $ O(n^2) $

Wenwei Lin · 2022 — 2025

最短路 ​

最短路