【考试】信竞思维引导体系

$$\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)$时间内计算出逆元 # 逆熵 逆熵可以让思路更有逻辑性，否则凭空思考正解完全是在碰运气 ## 二分法 遇到最大值最小 / 最小值最大问题，一般可以用二分答案来处理 ## 排序法 把所有东西（包括数组，边权，甚至询问等）都排序，然后用贪心处理 ## 假设法 假设要求的东西有序，再结合排序法推出第一个线索，然后继续推理 ## 倒推法 先让熵值降低，然后在低熵环境下推理，此后再考虑如何降低熵值 # 暴力 ## 纯模拟 出错几率小，但时间复杂度起飞 不失为狗急跳墙之策 考场上遇到做不来的题目一定要打个暴力骗分，分数比手段更重要 ## 模拟退火 用于处理单峰函数的最值问题 时间复杂度可控，随机次数越多答案越准确 ## 打表 如果答案只跟较少的一些参数有关，那么可以直接用暴力打出一份答案表 必须挂机，需要耐心与信仰 若发现挂机耗时太长，可以分组打表 / 多线程挂机