星光light

前缀函数 前置 子串 字符串中连续的一段。 前缀 指从字符串开头到某个位置结束的特殊子串 真前缀 指从字符串开头到某个位置结束的特殊子串（不包含字符串本身） 后缀 指从某个位置开始到字符串结尾的特殊子串 真后缀 指从某个位置开始到字符串结尾的特殊子串（不包含字符串本身） 定义 对于一个长 \(n\) 的字符串 \(s\)，我们设 \(i\) 位的前缀函数为 \(\pi_i\) 若 \(s\) 的子串 \(0\sim i\) 有一对相等的真前缀与真后缀，则 \(\pi_i\) 为真前缀（真后缀）的长度。 若不止一对相等的，令 \(\pi_i\) 为最长的长度。 若没有，则 \(\pi_i=0\) \(\pi_0=0\) 计算方法 朴素（暴力） 枚举：\(O(n^3)\) 优化一 简单思考一下，\(\pi_{i+1}\) 的值至多为 \(\pi_i+1\) \(O(n^2)\) 优化二 在寻找真前缀与真后缀时，我们会枚举一个长度 \(j\) 当匹配失败时，我们希望找到仅次于 \(j\) 的长度 \(j^{(2)}\)，其中 \(j^{(2)}\) 我们希望他满足前缀性质。 所以，\(j ...

树——二叉搜索树 Date:2023.1.14 定义 二叉搜索树是一棵二叉树，具有以下定义： 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。 二叉搜索树的左右子树均为二叉搜索树。 一些操作 先看变量： \(lc_x\)：x点的左儿子 \(rc_x\)：x点的右二子 \(val_x\)：x点的值 \(cnt_x\)：x点值的数量 \(siz_x\)：x点子树的数量 插入 向树中插入一个值 递归插入 与当前节点比较，若权值小于它，加入左子树，反之加入右子树 若当前点权值与插入值一样，当前点 \(cnt++\) 若当前节点为空，将节点设为当前节点 插入时注意更新变量 不要忘记更新父节点的儿子 删除 在树中删除一个值 先在树中查找该值节点 设改点为 \(x\)，分类讨论 若 \(cnt_x>1\)，将 \(cnt_x--\) 若 \(cnt_x=1\) 若该点是叶子节点（没有儿子），删除该节点 若该点只有一个儿子，返回它的儿子 若该点有两个儿子，返回左子树的最大值或右 ...

网络流——最大流算法dinic Date:2023.1.9 过程 整体来说，dinic 是不断 bfs分层+dfs增广 的过程 bfs分层 每个点的 层数 即为它到源点的最短距离，源点的 层数 为 0 通过它，我们可以发现： 1.当汇点没有 层数 时，算法结束 2.当每次搜索只搜比当前点 层数 多一的点，我们找到的肯定是最短增广路 至于怎么分...... 不会有人不会吧 dfs增广 先看一些变量： \(s：源点,t：汇点，ans：最大流\) \(c：边的容量\) \(f：边的流量\) \(sum：一次dfs的流\) 运用分层，我们可以轻易的找到最短增广路 从起点开始，每次往下进行搜索，只搜比当前 层数 多一的点，且管道的 \(c>f\) 当搜到 t 点，结束 dfs ，继续分层 两个优化 1.多路增广 该优化可让你一次搜到多条增广路 思路 当你从某个点回退到上一个点时，若该点 \(流量>0且还有其他可走路径\) 那我们就考虑对其再进行 dfs 2.当前弧优化 该优化可帮你避免不必要的搜索 思路 我们知道，当一条边 \(c=f\) 时，他就没有用了 这时，我们可以考虑避免对这 ...

网络流——最大流算法EK Date:2023.1.9 简介 EK 算法，即 Edmonds-Karp 动能算法，是求解最大流的基本算法。 反向边 反向边 是帮助程序能发现更优解 例： ---->A---->B----> 发现了一条 增广路 但后面发现： ---->C---->B----> ---->A---->D----> 这样比原方案更优 所以要建立一条 反向边，B---->A，让流过去的水能够流回来 下面讲一下建 反向边 方式： 链式前向星（链表） 在添加 正向边 时，也把 反向边 给添加（容量为0）。 这样对于第 i 条边的 反向边 是 \(i\oplus 1\)（编号请从偶数开始存，虽然奇数也不会错（玄学）） 邻接矩阵 这难道还要我说？ 过程 整体来说，就是一个不断 bfs+增广 的过程 为了方便讲解，我们在此定义一些变量： s：源点,t：汇点，ans：最大流 c：边的容量 f：边的流量 l：点的流量 bfs 每次从源点出发，进行搜索，若寻找到t，结束 bfs 进行增广。 假设现在我们要从 x->u 1.先判断能 ...

矩阵 Date:2023.1.13 定义 矩阵是一个 \(n\) 行 \(m\) 列的的表格 也可以看成一个二维数组 矩阵乘法 方法 设 \(A\) 为 \(m*d\) 的矩阵，\(B\) 为 \(d*n\) 的矩阵 \(C=A*B\) 则 \(C\) 为 \(m*n\) 的矩阵 \(C_{i,j}=\sum\limits_{k=1}^{d}A_{i,k}*B_{k,j}\) 即： \(\begin{bmatrix}a1&a2\\a3&a4\end{bmatrix}*\begin{bmatrix} b1&b2\\b3&b4\end{bmatrix}=\begin{bmatrix}c1&c2\\c3&c4\end{bmatrix}\) \(c1=a1*b1+a2*b3\) \(c2=a1*b2+a2*b4\) \(c3=a3*b1+a4*b3\) \(c4=a3*b2+a4*b4\) 例： \(\begin{bmatrix}5&5 \\6&7\end{bmatrix}*\begin{bmatrix}3&2 \\7&a ...