星光light

AC 自动机 很多人在第一次看到这个东西的时侯是非常兴奋的。不过这个自动机叫作 Automaton，不是 Automation，这里的 AC 也不是 Accepted，而是 Aho–Corasick（Alfred V. Aho, Margaret J. Corasick. 1975）。 前置 Trie （字典树） KMP （只要失配指针的思想即可） 定义 AC 自动机是 以 Trie (字典树) 的结构为基础，结合 KMP (字符串匹配) 的思想 建立的自动机，用于解决多模式匹配等任务。 构建 先简单解释一下： AC 自动机由两部分组成： 将模式串构造成一棵普通的 Trie。 利用 KMP 思想构造失配指针。 失配指针 同 KMP 一样，AC 自动机同样构造一个 fail 用于失配时的跳转指针。 但 AC 自动机的 fail 指向当前状态的最长后缀。 定义如下变量： 当前节点 u，u 的父亲节点 p，p 和 u 间用一条字符 c 连接。 字典树的边集 tr。（tr[u][c] 表示节点 u 的 c 出边的点） 假设所有深度小于 u 的 fail 指针均已求得。 若 tr[fa ...

∵To chase a girl needs time and money. ∴ Girl = Time × Money ∵time is money ∴ Girl = Money2 ∵money is the root of evil. $\therefore Girl\ =\ (\sqrt{Evil})^2$ ∴ Girl = Evil 重点词解释： chase n. 追求 root n. 根；根源 evil adj. 邪恶的

计算几何 三角函数 $\sin{\alpha}=\frac{b}{c}$ 正弦函数：对边比斜边 $\cos{\alpha}=\frac{a}{c}$ 余弦函数：邻边比斜边 $\tan{\alpha}=\frac{b}{a}$ 正切函数：对边比斜边 向量 …持续更新

数论 Date:2023.1.14 素数（质数） 定义 只有两个因数的数叫做质因数（1和它本身） 1 既不是素数也不是合数 判断素数 朴素算法 枚举 2 − (n − 1)的所有数字，判断其是否能被整除，时间复杂度：$\color{orange}O(n)$ 或者可以优化一下，枚举区间改成 $2-\sqrt{n}$，时间复杂度：$\color{orange}O(\sqrt{n})$ 埃式筛法 对于多个大数，朴素算法显然慢了 对于求多个质数，我们可以运用标记思想 我们知道，对于一个 x ∈ Z，它的倍数一定是约数 所以我们可以从小到大的枚举 n 内的质数，标记它的倍数，没被标的即是质数 时间复杂度：$\color{orange}O(n\, In\, In\,n)$（In n表示logen） 123456789101112131415161718192021#include<stdio.h>#include<cmath>#define N 10005using namespace std;int n;int f[N],ss[N],cnt;void ssai(i ...

operator浅谈 前言 operator，即c++的重载运算符。 可以理解为定义了一个符号的运算规则，用来更方便处理高精度等特定运算。 使用须知 =赋值运算符、[]下标运算符、()函数调用运算符、 − >成员访问运算符。 只能作为类成员重载，不能作为友元函数。 还有，重载后无优先级，可以打括号。 Finally，你不应该重载 && ∥∥ & 运算符，他们在程序中有重要的作用。 使用 你应该把他定义在结构体里，他不会对结构体外的运算符产生影响。 123{结构体名} operator {运算符}({运算符}){ {重载规则}}    例题 单讲不好讲，上一道例题：高精度a+b 1234567891011121314151617181920212223242526272829303132333435363738#include <bits/stdc++.h>using namespace std;struct high { int le ...

网络流——最大流算法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 点的层数为 di 当我们结束了一次 dfs（没有路可走），我们就要更新层数 遍历 i 的所有连点 (c>f)，找到连点中最小的层数，设为 dj 令 di = dj + 1 若点 i 没有连点，令 di = n 另外，我们不难发现，当 ds ≥ n，增广路已被搜完，结束循环 优化 当前弧优化 时间复杂度：$\color{orange}O\left(n^2m\right)$ G ...