问题描述 SAT(satisfiabality) 是适应性的缩写，一般称 k 的适应性问题为 k-SAT。适应性问题指有 \(n\) 个布尔变量 \(\{x_i\}\)，加入一些限制然后求限制内的解的问题。 因为 \(k>2\) 的 k-SAT 问题是 NP 完全问题（没有一定的算法和正解），我们只讨论 2-SAT 问题。 Tarjan 一般来讲，我们会想到把变量 \(x...

AC来自一个大佬的名字，并不是写了就可以自动AC的意思 XD AC自动机是建立在trie树上的一种优化手段。trie在每次查询一个字符串时，如果在一个子树查不到就会回溯再查，效率会很低。我们考虑在给每个节点加一个如果查不到就跳转的指针fail，那么如果找不到的话直接跳转到fail就可以了。fail代表的是拥有该点的最大后缀的点的位置。 那么怎么寻找这个fail呢？因为我们要寻找最大后缀，...

我之前一直记的迪杰斯特拉的翻译导致我把 dijkstra 写成了 dijstra 或者 dijskra…… 我以后叫她迪杰克斯歘！ dijkstra 是用来在有向图或者无向图中寻找任意两个点的最小距离的算法。但是无法处理带负环的图和求最长路。 dijkstra 的核心思想是由已找到的最短路的点集每次扩展一个点的最短路。 dis 数组代表由起点到其他点的最短路，初始化其为 \(I...

Guass消元 约旦·高斯消元法 求线性方程组 我们用一个\(n*(n+1)\)的矩阵存储线性方程组各项系数和零次项系数。 每一次找到一个未知数系数最大的方程，交换当前行方程和该方程，并将其他行该未知数的系数化为零。 重复n次即可。 最后第\(a[i][i]\)个数就是第i个未知数的系数，\(a[i][n+1]\)是等式右侧的数，用后者除以前者即可。 当化第i个方程时...

KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 算法。 问题：求 a 字符串与 b 字符串中子串相同的串首位置。 暴力就不说了，设 a 长 \(m\)，b 长 \(n\)，每次枚举比对每个字符，复杂度 \(O(nm)\)。 KMP 主要思想：如果一个字符串的子...

LCT维护一个森林，即把每个节点用splay维护，可以进行许多操作： 查询、修改链上的信息 随意指定原树的根（即换根） 动态连边、删边 合并两棵树、分离一棵树 动态维护连通性 等 主要性质 每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径，且中序遍历Splay得到的每个点的深度序列严格递增。 每个节点仅包含于一个splay中。 边分为实边和虚边...

矩阵树定理 定义 邻接矩阵：\(A=(a_{ij})\)，其中 \(a_{ij}\) 表示 \(i\) 到 \(j\) 有几条边相连。 度数矩阵：\(C=(c_{ij})\)，为对角矩阵，其中 \(c_{ii}\) 表示 \(i\) 的度数。 基尔霍夫矩阵：\(D=C-A\)。 余子式：\(M_{ij}\) 表示去掉第 \(i\) 行第 \(j\) 列后得到矩阵的行列式。 ...

主定理（Master Theorem）通常是指在算法分析领域中的一个定理，特别是用于分析递归算法的时间复杂度。 时间复杂度相关定义 在计算机科学中，算法的时间复杂度（time complexity）是一个函数，它定性描述该算法的运行时间。其原理在于，将计算机的每种基本运算（如加减乘除）所需的时间视为常数，然后考察一个算法调用了多大量级的基本运算。时间复杂度常用大 \(O\) 符号...

“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”——《孙子算经》 中国剩余定理 即求多个同余方程的解。 举个栗子。求一个数x，使得： \[\begin{cases} x≡2\pmod 3\\ x≡3\pmod 5\\ x≡2\pmod {11}\end{cases}\] 设 \(M=3*5*11=165\), \(a1=3\), \(a2=5\),...

前言 前几天考试了发现这个东西完全不会欸……学了又忘真是讨厌至极 QAQ 所以又在网上找着看了看写一篇博客备忘。 学习笔记真的很有用！ 分层图 这个很容易理解，来源就是在一些最短路的问题上题目又加了比如说主角可以用传送宝石进行折跃之类的问题（针对），即可以选择k条边把这些边的边权变为零。 怎么样解决呢？可以在原图的基础上多复制k个相同的图，并用k条边把图之间的边用0边权边相连。就...