「批注」大纲

LCat90 / 2024-10-21 / 原文

去年写的那个 trick 真的成小丑了感觉。

鉴于个人能力与未来发展方向，故只写 8 级以下知识点。

dp 和贪心可能会单独写。dp 参考。

last upd on: 10.18 23:16

2.1 入门级

2.1.3 数据结构

huffman 树：求最小权的树，权定义为所有点权值乘深度的和。
- 荷马史诗里面要求儿子不超过 $k$，需要补 0 过后用堆贪心，每次选小的早一步合成作为更深点。
栈：注意 csps2020 回文一题中先讨论第一步然后转化成两个栈问题。

2.1.4 算法

4. 数值处理算法高精度

一般来讲 __int128 就够了。

高精除以低精：考虑大除法，当前要计算的就是 r 和 b 的除，而 r 就是原数到这一位的取模。Submission。

5. 排序算法

冒泡排序：考点较多，参考 noi online s 那一道以及模拟赛 T2，都是逆序对的转化以及考虑一个元素前面有多少个比他的大，记为 $f_i$。（一轮排序后 $f_i$ 如果非 0 则改变 1）
计数排序，基本上没用。注意下面代码最后一行倒叙遍历是考虑情况：值相同但要保留输入顺序。

void counting_sort() {
  for (int i = 1; i <= n; ++i) ++cnt[a[i]];
  for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
}

2.1.5 数学与其他

更相减损术的高级运用：P10463 Interval GCD。维护差分数组，就可以做到单点修改，区间查询 gcd。

2.2 提高级

2.2.2 C++ 程序设计

set 方面注意 ODT 的写法。Sample。
- split 是将一个段分开，并返回以 $x$ 为开头的迭代器。update 中要先 split 右边，erase 删除是左闭右开。如果你先 query 再 upd 复杂度就是正确的。
- 对于一般的题目随机数据下期望满分。可用于乱搞。
注意 map 可以优化某些状态数大，但可用状态不多的 dp。可以用于普通 dp 的乱搞。详见。

2.2.3 数据结构

1. 线性结构

st 表在 query 时分成的两个区间是相交的，可以根据这个东西处理一类 $f(L,R)=\bigcup f(l_i,r_i)$，并要求 $(l_i,r_i)$ 相交的问题：CF1707E。
利用双栈维护双端插入删除，均摊复杂度线性。

2. 集合与森林

并查集可以维护序列里面一段连续的 0/1。

3. 特殊树

BIT 上二分的写法：记住 $Sum(S)=Sum(S/\operatorname{lowbit(S)})\operatorname{ op } f(S)$。从大到小枚举 bit 即可。Sample。
Trie 的全局加 1 操作：倒着建树，每次交换左右儿子，并递归到交换之后的 0 儿子。Sample：fusion tree。
笛卡尔树：注意构造方法，维护一条单减链。每次单调栈扫完之后建边。
- 树上 dp，给个例子。
平衡树：序列问题要维护相对顺序，使用文艺平衡树。注意 split 的引用参数写法。真题：列队。
- 以及和线段树类似的 pushup。放驼使。

5. 哈希表

字符串哈希：一般取单模数 $10^9+7$。
树哈希：找到重心，调用 xor shift 做和哈希。如果有两个重心就取哈希结果的 min。
和哈希/异或哈希：判断两个可重集是否相等，考虑 xor shift 的写法，注意为了防止被对着卡，mask 变量可以设计成随机数。

mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count()); // 推荐种子
ull shift(ull x) {
  x ^= mask;
  x ^= x << 13; x ^= x >> 7; x ^= x << 17;
  x ^= mask;
  return x;
}

为了避免哈希冲突，对于有 2 个相关联的哈希的题目，应使其哈希方式不同。比如一个使用和随机数，另一个使用 xorshift 后进行累加。Sample。
某些题目：。

2.2.4 算法

3. 分治算法

某些矩阵计数的题可以考虑分治列，然后枚举上下行的边界，计算跨过 $mid$ 的贡献。注意每次要对于跨度大的一维分治，这样分治总的复杂度才是 $O(nm\log n)$。
这道题是先考虑了 $S=2$ 的情况，然后发现每次跨越 $mid$ 时，每一列只需要指定匹配于另一列就一定可以通过后续调整有解。所以相当于是做 $\log 2^k$ 次 $S=2$ 的情况就等价到了 $S=2^k$。（注意很多时候题目都会提示 $S=2^k$ 这种信息，一定要考虑到分治）
cdq：考虑左边对右边的贡献，很多时候为了方便计算，通常先计算左边，然后让左右各自内部排序，计算跨越 $mid$ 的答案，然后再计算右边。
整体二分：算法思路是对询问和修改分治，把答案在 $mid$ 两边的都分开。多数题目都是【求第 $k$ 大】，这时要把小的那边的询问减去大的那边的个数。可以看道基础题。

5. 字符串相关算法 KMP only

建议频繁复习。筛选了好久选出来的讲解。本质上是一旦失配就一直向前跳 border。
Tips：能用 hash 的时候尽量用，最后才想 Kmp，比如这道题直接哈希加暴力就过了。（谁不更喜欢思维量更小的做法？）
bitset 在字符串匹配里的妙用。这玩意好写好用到离谱。
border 理论。
（后面看到还有一些 8 级的字符串算法，暂时可能不会总结，如果我后面写了会把这句话删掉的。）

6. 搜索算法

注意有个算法叫折半搜索 / meet in the middle。可以将时间复杂度开方。例：真题使方案数减半。
A*：设计估价函数 $H(i)$ 表示最优情况下 $i$ 状态到终点的花费，若此时已经超过限制/劣于当前最优解，那么不必再搜索。
- 可用优先队列维护 $F(i)+H(i)$，每次取最优的更新，保证第一次可以找到最优解。可能的应用：K 短路。
如果你写暴力/搜索，时刻注意能否记忆化，说不定会多很多分。

7. 图论算法

二分图：一些拓展。
- 判定有两种方式：1 是 dfs 点染色；还有 2：扩展域并查集（线段树分治会用）。
- 匈牙利匹配的复杂度是 $O(nm)$，多数情况都不满。给个比较综合的题。
- 某些图论题可以考虑二分图和奇环的时候分别怎么做，最后拼在一起即可。
欧拉回路：《当看到图论题没有思路时，想想欧拉回路》
- 欧拉回路构造方法：当前弧优化，dfs 完后入栈。不涉及构造，但涉及思想。
- 一类套路题是把问题转化成图论模型后，要求把所有边重定向，使得每个点入度和出度相同。此时可以考虑欧拉回路，记录每条边是正是反。例题：1 2 3。
- 有时要求入度和出度相差不超过 1，可以加入一个超级源点，连向所有奇点（只有偶数个）。
有向无环图（DAG）：
- 可以反向边 topo dp。
- 可以状压枚举子集给图分层 / dp。
双连通图：注意 tarjan 的写法。下面主要是记录一些结论，也可能有强连通分量。
- 边双严格强于点双。即：一个点双一定是边双。
  - 考虑构造图：一个点上面接 2 个只有这个公共点的环。
- 点双中若包含一个奇环，则所有点都在至少一个简单奇环上。出处。
- 若点双中没有偶环，则其中只有 1 个奇环。出处。
- 给图加最少的边使其是一个大边双：边双缩点后的树的叶子数量对 2 上取整。出处。
- 一定存在一种为一个边双连通分量中所有边定向的方案，使其成为一个强连通分量。出处（构造方案）。
- 论文题（Alex 的题解里面涉及了很多点双的结论）。结论题。
最小生成树：(B?????)
- Kruskal 重构树
最短路：
- Floyd 算法：
  - 可以用于求传递闭包，bitset 优化至 $O(\frac{n^3}{w})$。
  - 动态修改一条边每次更新多源最短路复杂度每次是平方。
- SPFA：
  - SLF 优化：
```
if (q.size() and dis[q.front()] >= dis[v]) q.push_front(v);
else q.pb(v);
```
  - 差分约束：求最小值则求最长路，否则最短路。详细见。不保证一年前我理解正确。
- Dijkstra：
  - 根据其松弛的思想，可以解决许多有后效性的环 dp，即每次强制选择最符合条件的那一个环上的入队。Sample 1 2。
- 最短路树/图：例题
  - 很多时候只选择一个最短路建树是完全不影响的。
  - 显然：只有更改最短路树上的边才有可能影响最短路。
  - 最短路图如果有向则一定是一个 DAG。
LCA：几种求法和代码。维护路径简单信息：倍增；复杂信息：树剖；要求快速查询：欧拉序。
树的重心、直径：
dsu on tree：

8. 动态规划

树形 dp / 背包：
- 树上背包的平方写法。
- 换根 dp。
- 某些 dp 例如：$dp_{x,0}=\sum dp_{to,1} \prod_{v\neq to} (dp_v+1)$。要乘上逆元，但是无法处理除数为 0 的情况。此时可以需要维护前后缀积。
- 可能有时候需要考虑是否随便选 1 个根就可以计算所有答案了。
  - 如果不行可能需要换根 / 点分治优化 dp。比如经典连通块背包。
  - 或者把每个根都跑一次，最后去重。Sample。
- 树上依赖/连通块背包：很多情况都是要子树合并，通常复杂度是 $O(m^2)$。此时我们按照 dfn 的倒序，每次对 $f_i$ 加入单点：$(f_{i+1},I(i))$ 或者 $f(r_i+1)$。其中 $r_i$ 表示 $i$ 的子树内最大的 dfn。每次单点加入的复杂度就是 $O(m)$ 了。
状压 dp：
- 枚举子集的复杂度是 $O(3^n)$。枚举子集的子集复杂度是 $O(4^n)$。

2.2.5 数学与其他

~~原谅我数学太菜，所以可能会写一些 sb 的东西。~~

宣传一下：总结 1 总结 2。

2. 初等数论

欧拉定理：若 $\gcd(a, m) = 1$，则 $a^{\varphi(m)} \equiv 1 \pmod m$。
欧拉函数：注意欧拉反演：$n=\sum_{d|n} \varphi(d)$。应用。
威尔逊定理：任意 $p$，都有 $(p-1)!\equiv -1 \pmod p$。应用。
裴蜀定理：设 $a_1, a_2, \dots, a_n$ 均是不全为零的整数，若存在整数 $x_1, x_2, \dots, x_n$, 使得 $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n=d$，则 $d = \gcd(a_1, a_2, \dots, a_n)$。应用。
扩展欧几里得算法：解方程 $ax+by=1(a\bot b=1)$。也可以推广到解 $ax+by=c$，但必须 $\gcd(a,b)|c$。
- 该算法求出的解满足：$|x|+|y|$ 在所有解中最小。
- 可用于求解逆元 $ax\equiv 1\pmod p$，故要求 $a\bot p$。
中国剩余定理。

3. 离散与组合数学

组合、排列：
- 圆排列
- 盒子与球：
- 卡特兰（Catalan）数：
容斥:

4. 线性代数

矩阵：
- 邻接矩阵自乘 $k$ 次方就是图上恰好走 $k$ 的到达情况。
- 很多时候可以加入一个一维向量来降低矩乘的复杂度。
  - 判断矩阵 $A$ 和 $B$ 相乘是否等于 $C$。我们引入随机一位向量先和一个矩阵相乘进行行列压缩，这样 $A,B$ 再相乘就是平方。正确性见题解。
- 很多时候事件是分段的，我们可以对每一段都做矩阵乘法。Sample 1 2。
- 某些题并不支持 $O(L^3)$ 的运算，此时我们需要式子变形使 $L$ 变小。一种方法就是把矩阵乘法根据结合律改变乘法的顺序。
高斯消元：
- 当环 dp 变量数过多时，考虑计算出一部分没有后效性的 dp，然后再用高斯消元求解有后效性的部分。[这里]
  (https://www.becoder.com.cn/contest/5595/problem/4)将 $O(n^{4.5})$ 优化到了 $O(n^3)$。
- 部分稀疏矩阵的高斯消元可以优化到线性。Sample。
线性基：
- 环上最大异或和直接暴力 dfs，进了一个环就直接把当前异或和加进线性基即可。

2.3 NOI 级

2.3.2 数据结构

1. 线性结构块状链表

大致是每根号个元素放进一个数组，然后相邻 2 个根号块用链表连起来。（还没学）

3. 复杂树

5. 可持久化数据结构

主席树：
- 在树上可以按照深度 / dfn 序建。
- 标记永久化：可持久化过后不支持 pushdown 操作，所以我们不下传操作；在询问的时候一路累加标记即可。参考。
可持久化并查集。本质是可持久化数组。某些时候可以和 kruskal 重构树互换。

2.3.3 算法

1. 算法策略

分块：
- 值域分块（治）：以阈值 $B$ 为分界，设置不同复杂度的算法，然后结合。可以理解为把 2 个暴力拼起来。Sample1 2 3。
- 数论分块：
  - 向上取整：对 $x/i$ 向上取整等价于 $(x+i-1)/i$ 向下取整。实现。
  - 如果每次计算是 $O(\sqrt{\frac{V}{i}})$ 的，整体复杂度就是 $O(V^{3/4})$。Sample 1 2。
- 序列分块：
  - 根号重构。
离线处理思想：
- 莫队：
- 离线树状数组：
复杂分治思想：线段树分治。
- 不要使用基于均摊复杂度 / 难以撤销的算法。如并查集不可路径压缩。
- 注意所有数据结构在当前分治完后都要回退到之前的状态。例如并查集需要用栈来存储每次更改，最后依次撤销。
- Sample 1 2 3 4 5。
构造：~~《移球游戏》是NOIP 2020竞赛中的一道构造题，这道题目深刻考察了选手的思维能力和解决问题的综合能力……~~
- 极力推荐。这里面应该总结了 jly 论文里的题目。
- 对于多个位置的还原问题，想想 3 个怎么做，然后延伸到 $n$ 个。（一般情况下 2 个是不行的）Sample 1 2。
- 多打表。在小数据的多种构造方式中选择最容易推广的那一种。Samlpe。

3. 图论算法

基环树：总结。
- 找环建议直接 dfs。
- 核心就是先想树怎么做，然后再想环，最后再想树 + 环怎么做。
- 某些题还可以考虑删掉环上某一条边，变成树的问题。但是复杂度平方。Joker。
2-SAT：
- 线性做法：注意解的构造根据 $i$ 和 $inv(i)$ 中谁 scc 编号更小输出。（scc 大小是逆 topo 序，scc 大的先被遍历）
- 平方的 dfs 做法：可以用于构造满足字典序限制的解。这道题做法就是枚举前面几位相同，再判断后面随便填是否合法，当然还是要尽量选择小的。（注意这里平方都指 $O(nm)$）