$$\huge\textbf{信竞思维引导体系}$$ 前言 信竞知识点也差不多要学完了，得整理整理思路了。碰到一个题目也得从不同的方面去考虑；能简化的就简化，千万不要为了一些无意义的东西伤脑筋。算算复杂度也就大概知道可能用到哪些算法了。

搜索

暴搜

包括 bfs / dfs ，用于小数据骗分 / 标程对拍 std 代码

一般 dfs 应用范围大于 bfs

剪枝技巧

优化搜索顺序

改变搜索顺序，使得潜在状态量以最快速度减少（靶形数独）

等效冗余

如果两个状态导致的结果相同，则只选择最优的状态进行扩展（引水入城 / Mayan 游戏）

可行性剪枝

最优性剪枝

其实就是$A^*$的弱化版，记录到达某个状态的最小花费，如果某次搜索时发现开销比以前大，则剪掉搜索枝

双向广搜

用于时空开销非常大，但对半砍（Meet-in-Middle）后就可接受的搜索题目

一般用于$O(8^{16})$ 变 $O(2\times8^8)$的题目

迭代加深搜索

用于根本不知道范围 / 无法获知搜索上限的题目（如埃及分数）

启发式搜索

用于可以写出$f(n)=g(n)+h(n)$，其中$h(n)\leq h^*(n)$的估价函数的搜索

可处理$k$短路 / 一些与曼哈顿距离有关的路径问题

还可处理可乐观估计剩余步数的图形 / 数字变换问题

另外可以用启发式搜索理论优化迭代加深搜索

记忆化搜索

用于数位 dp / 某些统计方案数的问题

图论

常用方法：建反图，建虚点，边排序

最短路

Dijsktra

稠密图性能较佳，但碰上完全图就不能够加堆优化（否则会突然变慢）

不能判负环

SPFA

性能逊于 Dijsktra，但支持判断负环

可用于差分约束系统（线性不等式与松弛方程类比）

Floyd

如果 MAXN = 50，那还是用它吧

本质思想类似动态规划

启发式搜索

由$h^*(n)=dis[n]$，直接进行启发式搜索即可（不过需要先建反图跑一次最短路，然后才能用A*），常用于解决$k$短路 / 其他动态统计最短路径的问题

最短路树

由最短路构成的树，常用于解决一些询问断边后最短路变化情况 / 统计最短路上的点的信息的问题

Tarjan

缩点

把一个图缩成 DAG 然后跑其他算法，常用艺能

割点

与图的连通性有关

割边

用于无向图缩点，把所有桥断掉以后跑连通块得到的就是 E-DCC

最小生成树

还有最大生成树，最小生成森林（建超级根）

Prim

每次找的是最小可扩展边

用得比较少，好像还更慢，所以不想管了

Kruskal

用并查集维护连通块

跑得很快，用得多一些

并查集 / 带权并查集

有些时候，把问题熵值降低就可以直接用（带权）并查集维护连通性了（比如 MooTube）

带权并查集的权值可以是许多东西（比如最小 / 最大值，节点权值和，甚至连通块直径），视题目而变

分层图

这个估计用不上，但是出现了类似“在图上共能进行$k$次操作”的题目就可以水掉

二分图染色 / 二分图匹配

用以解决两两配对问题

练习得较少，但遇到题目必须反应过来

欧拉回路

用于解决一笔画问题，所谓的边有可能是字母对 / 数字对等等

也可解决一些入度与出度相等点数的问题

树

构造

如果一个元素直接与三个元素有关，并且有一个元素较另两个元素特殊，那么可以把它们构造成一棵二叉树（比如跳跳棋）

在用遍历顺序来逆推树的结构时，必须知道中序遍历

倍增

主要应用于 LCA 上

偶尔也有倍增树形结构

LCA

只要是$log$级别的算法都可能被魔改到 LCA 身上（又是跳跳棋）

就一般的树来说，树链剖分的 LCA 要快于倍增

还有用 ST 表实现的$O(1)$查询写法

树上差分

求解树上两个节点的距离

加速树形 dp 的前缀状态计算

直径 / 重心

两树合并时的新直径问题

两树合并时的新重心问题

dfs 序 / 树链剖分

将树按照 dfs 顺序映射到一个区间上

解决子树 / 两点间路径修改 / 查询问题

数据结构

链表 / 双向链表

快速区间删除 / 维护节点连续性问题

单调栈

查询某元素向左 / 右遍历时第一个比它大 / 小的元素

单调队列

处理滑动窗口 / 定区间最值查询问题（可以用到动态规划中）

二维单调队列处理矩形内最大 / 最小元素问题

维护斜率优化中的凸包

优先队列

用于降熵后的贪心优化

自定义运算符的优先队列处理复杂模拟问题

优化 Dijsktra 中对最小边的查询

双优先队列维护定点两侧元素的最大 / 最小元素

手写堆

支持堆的合并操作

维护 Treap 的性质

Hash 表

$O(1)$查询字符串 / 巨大数字是否存在

可同时维护元素出现的次数等信息

ST 表

一般不可修改，但支持$O(1)$区间查询

查询时跑得飞快，可以用来优化掉某些非正解的$log$从而跑到正解的速度

还可以用来加速 LCA 的查询

树状数组

$O(logn)$单点修改，$O(logn)$区间查询

一般情况下比线段树快很多，可在魔改之后进行区间修改 / 区间查询，不过那还不如直接打线段树来得痛快

将树状数组看作一个桶，可以用于区间内元素个数的计算（数字不大太的逆序对问题）

线段树

$O(logn)$区间修改，$O(logn)$区间查询

全能性很强，可用于维护各种只与端点有关的可合并信息（如：直径，扫描线等）

动态开点线段树

又名值域线段树 / 权值线段树

某些题目中可看作一个动态桶，用于存储不进行离散化的元素信息

可以用指针来写，每次删除元素以后把空间 free() 掉即可避免内存爆炸

字典树

和哈希类似，用于查询字符串的存在问题

同样可使用指针和 free() 节约内存

平衡树

大部分的题目都可以用 set / multiset 水掉

如果碰上了 set 无法魔改 / 需要查询元素出现次数的情况，还是老老实实打非旋 Treap 稳一点（替罪羊过于玄学，Splay 易写错还更慢）

STL 相关

使用 STL 时一定要注意容器是否已空，否则会 RE

set / multiset

这两种容器是可以用迭代器按顺序遍历内部元素的，所以用处比较大

寻找冲突元素时可以采用重载运算符的方法（注意：在 set 当中，若$a\not <b$且$b\not<a$，则$a=b$），直接使用 s.find() 函数处理

set 还可以用来动态维护第$k$小元素，直接开个迭代器指向第$k$小元素即可，新加入元素不会对迭代器指向产生影响

vector

vector 实际上是很慢的，效率远不及数组，所以在图论当中需避免使用 vector 来存边，还是开链式前向星比较好

在哈希表当中用处最大，作为动态容器储存每个哈希值对应的元素

map

本质上是个平衡树，容器内元素越多效率越慢

广泛应用于搜索判重 / 查询复杂对应关系（string 到 int 可以用更快的哈希）

使用自定义结构体做下标时需要重载小于号

bitset

把一个数拆成二进制，比如 bitset<20> b(56) 表示开个$20$数位的二进制数存放$56$这个数字

输出时用遍历 cout 即可

做状态压缩的时候可以用来调试

动态规划

动态规划的核心是状态描述和决策转移，难点是复杂度优化

有些时候可以通过 $2e7$ 反算出需要优化掉哪些枚举，这样会使得优化更有目的性

背包问题

01背包

最简单的背包问题，为背包开桶进行动规

对容积的枚举是倒序的（物品唯一，不可叠加）

如果桶会爆炸，可以用模拟退火进行随机化处理

完全背包

常见于无限货币问题（付钱 / 找钱）

对容积的枚举是正序的（无限物品，可叠加）

可以用于优化某些情况下的多重背包方案数问题

多重背包

常见于有限货币问题 / 商品问题

可用二进制优化将物品数降至$log$级别，但无法处理方案数问题（完全背包 + 加法原理解决）

分组背包

每组物品只能选一件，那么用$f[i][j]$表示考虑前$i$组，背包容积为$j$时的状态

枚举时，对容积的枚举放在对组内物品的枚举之外，才能保证每组最多选一个物品

树上背包

如果碰到树形依赖关系的背包问题，可用$f[i][j]$表示以$i$为根的子树选$j$个节点 / 容积为$j$时的状态，转移方程类似 $f[u][i]=\max\{f[u][i-j]+f[v][j]\}$

树形动规

常用方法：$[0/1]$存放选与不选，对森林建超级根连接所有根（若有基环树还需要缩点）

用$f[i][\cdots]$来表示考虑以$i$为根的子树，一般是边 dfs 边转移状态

DAG 动规

一般缩点以后变成 DAG，就可以用 DAG 动规（类似 SPFA 思想）

DAG 动规过程实质上是个拓扑排序的过程

记忆化搜索

一般就是数位 dp

需要观察该如何描述一个数字的特征，每个特征分别用一维来存储

最长单调子序列问题

有$O(n^2)$做法和$O(nlogn)$做法

$O(n^2)$做法是用$f[i]$表示以$a[i]$结尾的最长单调子序列长度，然后每次枚举前缀状态（兼容性更好）

$O(nlogn)$做法是用 upper_bound() / lower_bound() 以及贪心思想优化前缀状态的枚举

变形后还可以用于求两个字符串的最长公共子串长度（最长公共子序列）

状压动规

如果遇到$n=10,n=12$之类的题就大概率是用状压

可以先把可行状态装到内存池中，节省枚举时间

区间动规

用$f[i][j]$表示$[i,j]$这个区间的状态，一般后边都会附着一维$[0/1]$来表示当前在左端点 / 右端点

有些时候第一层 for 循环需要枚举区间长度以保证前缀状态已知

还可以变形为$f[i][j]$表示一个东西的$[1,i]$区间到另一个东西的$[1,j]$区间的状态（比如字符串变换问题）

斜率优化

若发现 dp 方程可以整理为$b=y+kx$的形式，则可用单调队列维护一个凸包以优化寻找最小前缀状态的过程

有些时候数组可以滚动，但别把自己滚死了（比如反向 memcpy）

费用提前

遇到有后效性的费用计算时，为了兼容斜率优化，把后面的费用提前到现在计算以取消后效性

路径压缩动规

如果描述状态会导致空间爆炸，那就可以凭信仰进行路径压缩

一般路径压缩可能会用到 LCM 之类的东西

四维动规

$O(n^4)$解决在一个矩形内走出两条单调路径的问题

用$f[i][j][k][l]$描述一个人走到$(i,j)$，另一个人走到$(k,l)$的状态，再根据题目要求适当调整

齐线法

用于处理最大合法矩阵问题

用$l[i][j],r[i][j],h[i][j]$表示合法的最大可扩展宽度 / 高度，然后$O(n^2)$跑一遍所有的点统计答案

数论

差分

快速区间修改

处理一些贪心 ( NOIP 2018 D1T1 ) / 闭合匹配问题

前缀和

快速询问区间和

应用容斥原理的二维前缀和快速询问二维区间和

运用前缀和思想优化部分动态规划（费用提前思想）

辗转相除法

求解两个数的最大公约数 / 最小公倍数

加速某些具有更相减损特性的计算（比如跳跳棋）

GCD / LCM 的性质

设$gcd(a,b)=g,\;lcm(a,b)=l$

则有$gcd(a/g,b/g)=1,\;gcd(l/a,l/b)=1$

因数枚举

$O(\sqrt{n})$枚举一个数字的所有可能的因数

注意如果一个数字$x$是$n$的因数，那么$n/x$也是$n$的因数，所以枚举时要注意处理这种情况；还要特判$\sqrt{n}$是否被多算一次

线性筛法

用桶筛质数

获得一个区间内所有质数

扩展欧几里得算法 (exgcd)

求解$ax+by=gcd(a,b)$方程

求解一个数在与其互质的数意义下的逆元（除法取模）

费马小定理

若$a,p$互质，则$a^{p-1}\equiv 1(\mod p)$

应用于逆元的计算，$a$在模$p$意义下的逆元即 $a^{p-2}$（可用快速幂加速）

中国剩余定理

求解线性同余方程组

欧拉函数

遇到求区间内互质对个数的时候可以用上

快速幂

使用二进制加速求解一个数的$p$次幂

矩阵 / 矩阵快速幂

加速求解线性递推式第$n$项

逆元递推

获得一个区间内所有数的逆元

可以设 $p=k\cdot i+r$进行推导，推导过程就是由 $k\cdot i+r\equiv0$然后两边同乘$i^{-1}$和$r^{-1}$，这里记住结论就可以了：$i^{-1}=(p-p/i)\cdot(p\mod i)^{-1}(\mod p)$

实际上还可以用于逆元递归，$x^{-1}=(p-p/x)\cdot(p\mod x)^{-1}$，递归边界设为当$x=1,x^{-1}=1$即可在$O(logn)$时间内计算出逆元

逆熵

逆熵可以让思路更有逻辑性，否则凭空思考正解完全是在碰运气

二分法

遇到最大值最小 / 最小值最大问题，一般可以用二分答案来处理

排序法

把所有东西（包括数组，边权，甚至询问等）都排序，然后用贪心处理

假设法

假设要求的东西有序，再结合排序法推出第一个线索，然后继续推理

倒推法

先让熵值降低，然后在低熵环境下推理，此后再考虑如何降低熵值

暴力

纯模拟

出错几率小，但时间复杂度起飞

不失为狗急跳墙之策

考场上遇到做不来的题目一定要打个暴力骗分，分数比手段更重要

模拟退火

用于处理单峰函数的最值问题

时间复杂度可控，随机次数越多答案越准确

打表

如果答案只跟较少的一些参数有关，那么可以直接用暴力打出一份答案表

必须挂机，需要耐心与信仰

若发现挂机耗时太长，可以分组打表 / 多线程挂机