何事秋。

数据结构基本算法

AC自动机(4) bfs/dfs(5) bitset(3) CF刷题(23) dp一般看规律(11) dp基本算法(12) KMP(2) LCA(1) LCT(4) Prufer(2) SAM(3) STL(1) tarjan(1) 主席树/线段树(14) 二分/三分(2) 二分图(1) 位运算(1) 偏序问题(2) 分块(1) 分治/点分治/边分治(2) 单调栈(2) 单调队列(1) 博弈/sg(3) 博弈论基本算法(11) 后缀数组(1) 启发式合并(1) 哈希(4) 回文自动机(2) 图论一顿套模板(3) 图论基本算法(31) 基本算法(2) 多项式(1) 套题(1) 字典树(1) 字符串基本算法(27) 容斥(1) 平衡树/堆(2) 并查集(3) 序列自动机(1) 快速幂/矩阵快速幂(1) 思维只会A+B(5) 投稿(2) 拓扑序(1) 数位dp(1) 数学不好先打表(4) 数据结构瞎乱写(8) 数论分块(1) 数论只会gcd(20) 数论基本算法(64) 暴力(1) 最短路(3) 期望/概率(1) 期望dp/概率dp(1) 构造(3) 枚举(3) 树形dp(3) 树链剖分(5) 模拟只会猜题意(5) 生成树(1) 签到题(2) 线性dp(12) 线性基(2) 组合数学(1) 组合数学靠运气(2) 结论题(2) 网络流/费用流(5) 网络流基本算法(5) 群论(2) 背包dp(1) 莫比乌斯反演(1) 莫队(1) 虚树(1) 计数类dp(1) 计算几何(8) 计算几何基本算法(15) 贪心刚好过样例(3) 随机化算法(2)

/ 注册

全部文章 / 数据结构基本算法（共69篇）

最小生成树——kruskal、prim

一、最小生成树简介：给定一张边带权的无向图G=（V,E），n=|V|，m=|E|。由 V 中的全部 n 个顶点和 E 中的 n-1 条边构成的无向连通子图被称为G的一棵生成树。边的权值之和最小的生成树被称为无向图G 的最小生成树（MST）。 1。任意一棵最小生成树一定包含无向图中权值最小的边。 ...

2020-09-04

0 584

最近公共祖先（LCA）

一、基本概念：给定一棵有根树，若节点z既是节点x的祖先，也是节点y的祖先，则称z是x，y的公共祖先。在x，y的所有公共祖先中，深度最大的一个称为x，y的最近公共祖先，记为LCA（x，y）。 LCA（x，y）是x到根的路径与y到根的路径的交汇点。它也是x与y之间的路径上深度最小的节点。求最近...

2020-09-04

0 468

树状数组

一、树状数组的基本应用：其基本用途是维护前缀和。对于给定的序列a，我们建立一个数组c， c（x）保存序列a的区间 [ x − ...

2020-09-04

0 395

线段树：

一、建树、单点修改、单点查询、区间修改、区间查询：单点修改、区间查询： #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algori...

2020-09-04

0 505

树上差分水题：

一、Network POJ - 3417：求多少条树边被非树边覆盖了零次或者一次：注意，若一刀就能使树不连通，那么也需要第二刀去切附加边。 1号节点的 cf 不算 #include<iostream> #include<cstdio> #include<algor...

2020-09-04

0 437

次小生成树：

一、P4180 【模板】严格次小生成树[BJWC2010]：因为是严格的，维护最大值和严格次大值就好啦。 #include<iostream> #include<cstdio> #include<algorithm> #include<cstring&g...

2020-09-04

0 438

曼哈顿最小生成树：

Object Clustering POJ - 3241 We have N (N ≤ 10000) objects, and wish to classify them into several groups by judgement of their resemblance. To simply...

2020-09-04

0 358

树上分治：

一、点分治。题目① Tree POJ - 1741： Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance bet...

2020-09-04

0 370

树链剖分：

这真是个神奇的东西。一、模板例题： P3384 【模板】树链剖分：题目描述如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：操作1：格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z 操作2：格式： 2 x y 表示求树从...

2020-09-04

0 579

最近公共祖先lca（2）：

之前学习过一次lca，是用暴力，倍增，tarjan离线处理的。之前就知道lca还有其他两种写法，不过那个时候还不会树剖，就没学。今天学习树剖之后，发现lca树剖写法不就是个裸的树剖吗。预处理 O（n）查询logn 比倍增还优秀一点。今天就补上没学的那两种lca的写法了。 P3379 【模...

2020-09-04

0 594