加载中...
2025-01-30好文收集
本站力推
详情
2025-01-30毒瘤题收集
本站力推
详情
2025-01-30更新日志
本站力推
详情
2025-01-30好文收集
本站力推
详情
2025-01-30毒瘤题收集
本站力推
详情
计算几何合集
计算几何 三角函数 \(\sin{\alpha}=\frac{b}{c}\) 正弦函数:对边比斜边 \(\cos{\alpha}=\frac{a}{c}\) 余弦函数:邻边比斜边 \(\tan{\alpha}=\frac{b}{a}\) 正切函数:对边比斜边 向量 ...持续更新
前缀函数
前缀函数 前置 子串 字符串中连续的一段。 前缀 指从字符串开头到某个位置结束的特殊子串 真前缀 指从字符串开头到某个位置结束的特殊子串(不包含字符串本身) 后缀 指从某个位置开始到字符串结尾的特殊子串 真后缀 指从某个位置开始到字符串结尾的特殊子串(不包含字符串本身) 定义 对于一个长 \(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 素数(质数) 定义 只有两个因数的数叫做质因数(1和它本身) \(1\) 既不是素数也不是合数 判断素数 朴素算法 枚举 \(2-(n-1)\)的所有数字,判断其是否能被整除,时间复杂度:\(\color{orange}O(n)\) 或者可以优化一下,枚举区间改成 \(2-\sqrt{n}\),时间复杂度:\(\color{orange}O(\sqrt{n})\) 埃式筛法 对于多个大数,朴素算法显然慢了 对于求多个质数,我们可以运用标记思想 我们知道,对于一个 \(x\in Z\),它的倍数一定是约数 所以我们可以从小到大的枚举 \(n\) 内的质数,标记它的倍数,没被标的即是质数 时间复杂度:\(\color{orange}O(n\, In\, In\,n)\)(\(In\, n\)表示\(log_en\)) 123456789101112131415161718192021#include<stdio.h>#include<cmath>#define N 10005using namespace std;int ...
二叉搜索树
树——二叉搜索树 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\) 若该点是叶子节点(没有儿子),删除该节点 若该点只有一个儿子,返回它的儿子 若该点有两个儿子,返回左子树的最大值或右 ...
operator浅谈
operator浅谈 前言 \(operator\),即c++的重载运算符。 可以理解为定义了一个符号的运算规则,用来更方便处理高精度等特定运算。 使用须知 \(=\)赋值运算符、\([]\)下标运算符、\(()\)函数调用运算符、\(->\)成员访问运算符。 只能作为类成员重载,不能作为友元函数。 还有,重载后无优先级,可以打括号。 Finally,你不应该重载 \(\&\&\;\|\|\;\&\) 运算符,他们在程序中有重要的作用。 使用 你应该把他定义在结构体里,他不会对结构体外的运算符产生影响。 123{结构体名} operator {运算符}({运算符}){ {重载规则}}    例题 单讲不好讲,上一道例题:高精度a+b 1234567891011121314151617181920212223242526272829303132333435363738#include <bits/stdc++.h>using namespace s ...
网络流--Dinic
网络流——最大流算法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\) 时,他就没有用了 这时,我们可以考虑避免对这 ...
网络流--ISAP
网络流——最大流算法ISAP Date:2023.1.12 简介 ISAP 和 dinic 十分相似,应该比较好懂 GAP 则是 ISAP 的优化 ISAP ISAP 算法,也是运用 bfs分层+dfs搜索 与 dinic 区别有两点: 1.只用了一次 bfs 分层,后续层数更新随着 dfs 一起 2.因为某些原因(dfs 更新层数),dfs 需要反跑(汇点->源点) 过程 因为 ISAP 的 dfs 需要反跑,知道大家肯定打不习惯 于是,我们可以反跑 bfs分层,就可以正跑 dfs(反跑时汇点层数为 0) dfs 时,过程与 dinic 基本相同,这里不详细展开 主要说如何更新层数: 更新层数 设 \(i\) 点的层数为 \(d_i\) 当我们结束了一次 dfs(没有路可走),我们就要更新层数 遍历 \(i\) 的所有连点 \(\left ( c>f \right)\),找到连点中最小的层数,设为 \(d_j\) 令 \(d_i=d_j+1\) 若点 \(i\) 没有连点,令 \(d_i=n\) 另外,我们不难发现,当 \(d_s\ge n\),增广路已被搜完,结束循环 ...
网络流--EK
网络流——最大流算法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.先判断能 ...
网络流--概念篇
网络流——概念篇 网络 网络表示一个有向图(可能有环),\(G=(V,E)\) 每条边 \((u,v)\in E\)都有一个权值\(c(u,v)\),称之为容量,对于$(u,v)E \(,均有\)c(u,v)=0$ 其中有两个点: \(s\in V\) 源点(没有入度) \(t\in V\) 汇点(没有出度) 流 设 \(f(u,v)\)定义在二元组 \((u\in V,v\in V)\)上的实数函数且满足 容量限制:对于每条边,流经该边的流量不得超过该边的容量,即,\(f(u,v)\le c(u,v)\) 斜对称性:每条边的流量与其相反边的流量之和为 0,即 \(f(u,v)=-f(v,u)\)  流守恒性:从源点流出的流量等于汇点流入的流量,即 $xV-{s,t}, {{(u,x)E}}f(u,x)={{x,vE}}f(x,v) $ 那么 f 称为网络 G 的流函数。对于 \((u,v)\in E\),\(f(u,v)\)称为边的流量,\(c(u,v)-f(u,v)\)称为边的剩余容量。整个网络的流量为 ,\(\sum_{(s,v)\in E}f(s,v)\)即 从源点发出的所 ...
矩阵
矩阵 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 ...
avatar
星光light
星光照耀,灿烂前行
Follow Me
最新文章
网站资讯
文章数目 :
34
已运行时间 :
348 天
本站总字数 :
31.4k
本站访客数 :
1037
本站总访问量 :
1639
最后更新时间 :
1 个月前