何事秋。
何事秋。
全部文章
数据结构基本算法
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
583
最近公共祖先(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
463
树状数组
一、树状数组的基本应用: 其基本用途是维护前缀和。对于给定的序列a,我们建立一个数组c, c(x)保存序列a的区间 [ x − ...
2020-09-04
0
393
线段树:
一、建树、单点修改、单点查询、区间修改、区间查询: 单点修改、区间查询: #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algori...
2020-09-04
0
504
树上差分水题:
一、Network POJ - 3417: 求多少条树边被非树边覆盖了零次或者一次: 注意,若一刀就能使树不连通,那么也需要第二刀去切附加边。 1号节点的 cf 不算 #include<iostream> #include<cstdio> #include<algor...
2020-09-04
0
436
次小生成树:
一、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
577
最近公共祖先lca(2):
之前学习过一次lca,是用暴力,倍增,tarjan离线处理的。 之前就知道lca还有其他两种写法,不过那个时候还不会树剖,就没学。 今天学习树剖之后,发现lca树剖写法不就是个裸的树剖吗。 预处理 O(n) 查询logn 比倍增还优秀一点。 今天就补上没学的那两种lca的写法了。 P3379 【模...
2020-09-04
0
594
首页
上一页
1
2
3
4
5
6
7
下一页
末页