Daowuu

分类

动态规划(1) 博弈论(1) 图论(9) 字符串(5) 数学(10) 数据结构(3) 未归档(1) 计算几何(8) 题解(2) 高精度(1)

/ 注册

TA的专栏 37篇文章 0人订阅

14篇文章 1388人学习

8篇文章 1010人学习

10篇文章 1691人学习

5篇文章 935人学习

全部文章（共41篇）

LCA 来自专栏

最近公共祖先 LCA（Least Common Ancestors），即最近公共祖先，指对于有根树 T 的两个结点 u 、v ，最近公共祖先 LCA(T,u,v) 表示一个结点 x, 满足 x 是 u、v 的祖先且 x 的深度尽可能大。树上倍增 int anc[maxn][32]; // 结点...

lca

2020-07-29

0 783

无向图的连通性来自专栏

割点和割边在无向图中，所有能互通的点组成了一个“连通分量”。在一个连通分量中有一些关键的点，如果删除它，会把这个连通分量分成两个或更多，这种点称为割点（cut vertex）。在一个连通分量中，如果删除一条边，把这个连通分量分成两个，这个边称为割边（cut eddge，又称为桥，bridge）。 ...

图论

2020-07-26

0 1210

序列自动机来自专栏

序列自动机序列自动机是一个可以快速判断字符串t是否是字符串s的子序列的一个算法。序列自动机基础初始化：对s构造序列自动机，使用代表从第i个位置开始，字符j出现的第一个位置。我们倒着遍历更新即可。 const int maxn = 1e6+1; const int inf = 0x3f3...

字符串序列自动机

2020-07-24

0 734

最小生成树（MST）来自专栏

最小生成树最小生成是无向图中的一个问题。 kruskal 算法时间复杂度，m 为边的个数对边进行排序。用并查集处理连通性问题。 const int maxn = 1e6+1; struct E{ // 图中的边 int u, v, w; }e[maxn]; //stru...

最小生成树图论

2020-07-23

0 696

最短路来自专栏

最短路径问题在一个图中有 n 个点、m 条边。边有权值，例如费用、长度等，权值可正可负。边可能是有向的，也可能是无向的。给定两个点，起点是 s，终点是 t，在所有能连接 s 和 t 的路径中寻找边的权值之和最小的路径，这就是最短路径问题。注：若图中存在负圈，则不存在最短路问题，若存在负边权，则不能...

2020-07-20

1 825

容斥原理来自专栏

容斥原理的基本概念在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理.注...

容斥原理数学

2020-07-17

0 870

全错位排列来自专栏

全错位排列的基本概念一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？数学公式证明：设1，2，3，…，n的全排列的集合为 S，而使的群排列集合记为，所以，又因为，由容斥定理可得： ,化简得：递推公式图示：

全错位排列数学

2020-07-17

0 603

树状数组

树状数组的概念树状数组是一种利用数的二进制特征进行检索的树状结构。树状数组基础长度为 n 的数列{a1,a2,a3,a4,....,an}，进行以下操作：单点修改：(x, val)，把 ax 加上 x。注：该点值修改完之后，会把值压缩给后面（箭头指向）的点。区间查询：（r）表示...

树状数组数据结构

2020-07-16

0 732

线段树

线段树的概念线段树是一种用于区间处理的数据结构，用二叉树来构造线段树是二叉树，一个区间每次被折一半往下分，所有最多分次就能找到。这就是线段树效率高的原因，使用了二叉树折半查找的方法。线段树的基本操作单点修改，区间查询【max】给定一个n（n <= 100000）个元素的数组A，...

线段树数据结构

2020-07-14

0 813

有向图的连通性来自专栏

强连通分量（SCC）如果一个有向图G不是强连通图，那么可以把它分成多个子图，其中每个子图的内部是强连通的，而且这些子图已经扩展到最大，不能与子图外的任意点强连通，称这样的一个“极大强连通”子图是G的一个强连通分量。 Kosaraju算法时间复杂度 O(N+E) Kosaraju 算法用到了“...

图论

2020-07-11

0 1255