NCC-79601 Captain's Log

NCC-79601 Captain's Log

To boldly go where no one has gone before.

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

posted on 2019-09-13 23:14:59 | under 考试 |

$$\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)$时间内计算出逆元

逆熵

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

二分法

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

排序法

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

假设法

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

倒推法

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

暴力

纯模拟

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

不失为狗急跳墙之策

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

模拟退火

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

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

打表

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

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

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