何事秋。
何事秋。
全部文章
分类
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)
数据结构基本算法(69)
数据结构瞎乱写(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)
归档
标签
去牛客网
登录
/
注册
何事秋。的博客
全部文章
(共461篇)
Tarjan算法与有向图连通性
一、基本概念: 流图: 给定一个有向图G= (V,E),若存在r∈V满足,满足从r出发能够到达V中所有的点,则称G是一个流图,记为(G,r),其中r是流图的源点。 流图的搜索树: 在一个流图(G,r)上从r出发,进行深度优先遍历(DFS),每个点只访问一次。所有发生递归的变(x,y)(换言...
2020-09-04
0
901
二分图的匹配
一、二分图的判定: 如果一张图的N个节点可以分成A,B两个非空集合,其中A∩B=空集,并且在同一集合内的点之间都没有边相连,那么称这张无向图为一张二分图。A,B分别称为二分图的左部和右部。 定理: 一张无向图是二分图,当且仅当图中不存在奇环(长度为奇数的环)。 根据该定理,...
2020-09-04
0
547
二分图的覆盖与独立集
一、二分图最小点覆盖: 给定一张二分图,求出一个最小的点集S,使得图中任意一条边都有至少一个端点属于S。这个问题被称为二分图的最小点覆盖,简称最小覆盖。 Konig定理: 二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数。 证明: 首先,因为最大匹配是原二分...
2020-09-04
0
558
网络流初步
一、简介: 网络流是图论中一个博大精深的分支。若要详细的学习网络流的各种模型与应用,需要不少时间。本篇文章的学习希望我自己可以建立对网络流的初步认识,内容比较浅显,少部分算法和证明的细节会被省略。 一个网络G=(V , E)是一张有向图,图中每条有向边(x,y)∈E都有一...
2020-09-04
0
469
Trie(字典树)
一、基本概念: Trie(字典树)是一种用于实现字符串快速检索的多叉树结构。Tire的每个节点都拥有若干个字符指针,若在插入或检索字符串时扫描到一个字符c,就沿着当前节点的c字符指针,走向该指针指向的节点。 初始化: 一棵空Trie仅包含一个根节点,该点的字符指针均指向空。 ...
2020-09-04
0
435
KMP
一、KMP: 时间复杂度O(N+M)。 next数组求法: (1)初始化next(1)= j = 0,假设next(1----i-1)已经求出,下面求解next(i)。 (2)不断尝试扩展匹配长度j,如果扩展失败(下一个字符不相等),令 j 变为next(j),直至 j 为0(应该开始从头开始匹配...
2020-09-04
0
408
最小表示法
一、最小表示法: 给定一个字符串S(1----N),如果我们不断把它的最后一个字符放到开头,最终会得到n个字符串,称这n个字符串是循环同构的。这些字符串中字典序最小的一个,称为字符串S的最小表示。 最小表示法求解: (1)我们先把S复制一份接到它的结尾,得到的字符串记为SS。 ...
2020-09-04
0
515
EX—KMP
一、基本概念: **问题定义:**给定两个字符串 S 和 T(长度分别为 n 和 m),下标从 0 开始, 定义extend[i]等于S[i]…S[n-1]与 T 的最长相同前缀的长度,求出所有的extend[i]。 来看下next[i]与extend[i]的定义: next[i...
2020-09-04
0
397
Manacher—马拉车
一、基本: 线性时间求最长回文子串。最长回文子串的长度为半径-1。 最长子串的长度是半径减1,起始位置是中间位置减去半径再除以2。 HDU----3068 最长回文: 给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba, a...
2020-09-04
0
366
AC自动机
一、基本: 当我们遍历到 某个 节点的时候,由于存在这个节点,我们就让他的fail指针 指向 他父亲节点的fail指针指向的那个节点的具有相同字母的子节点。 简单来说,AC自动机是用来进行多模式匹配(单个主串,多个模式串)的高效算法。 使用Aho-Corasick算法需要三步: 建立模式串的Tr...
2020-09-04
0
465
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页