《信息学奥赛 trick 杂录》
Chiesl
·
·
个人记录
持续更新ing...
欢迎各位在评论区分享经验，如若收录本文，我将注明贡献。
近七日更新：
无。
目录
Part 1. 动态规划
Part 2. 分治与离线
Part 3. 图论
-
树的中心
-
树的重心（猎奇性质）
-
树上点到链的距离公式
-
并查集的运用
Part 4. 计数技巧
-
所有子区间贡献求和（贡献与最大值最小值相关）
-
最大值与最小值之间的容斥转化
-
异或哈希
-
必要条件缩小枚举范围
Part 5. 字符串算法
Part 6. 数据结构
-
0-1 trie 的运用
-
动态开点线段树节点回收（卡常技巧）
-
通过 dfn 序遍历子树（卡常技巧）
引言
在信息学奥赛中，解决难题离不开日常的练习，而日常的练习如何积累成考场的思路，就要看平时对于经典 trick 的积累。
动态规划
连续段 DP
这个DP主要用于解决类似于“在一个数列中产生一个个连续块，求可能数”的动规问题。
比如，在一排连续的盒子中放苹果，连着的苹果都可视作一个连续块。
一般来说，我们都会考虑新加入的元素对原状态的影响。通常的，有三种情况：
-
加入的元素在原先某个连续段的两端。
-
加入的元素单独成为一个连续段。
-
加入的元素把两个连续段连成了一个。
值得注意的是，通常不考虑连续段的具体状态，而只考虑整体状态，如连续块数量与元素数量。
这里有一篇博客讲的非常好，刚刚的介绍也摘自这篇博客，%%%。
这里直接上例题，这里有这样一个问题。
刚刚的问题是模板题，如果报名了梦熊的炼石计划NOIP的话，你将在模拟考9中遇到一个相当困难的题目，与 P7967 做法几乎一致。
例题：
分治与离线
树链分块
适用于将问题建模后为在树上向根节点跳的问题，对于每个 i 维护跳出块所需的步数 f_i 和跳出去以后所在的位置 g_i，本质上是暴力。
对于部分动态树可以解决的问题，可以用这个 trick 来水过。
例题：
图论
树的中心
与树的重心不同，我们在解题时可以将直径问题转化为中心问题，以下将给出树的中心的定义与性质：
定义1： 以该点为根出发的所有路径的最长路最短。
定义2： 当一棵树以点 x 为根时，树的高度（深度）最小，则称 x 为树的中心。
性质1： 直径长度为偶数时，树的中心是唯一的一个点；
性质2： 直径长度为奇数时，树的中心是 一定相邻 的两个点，也可看作是唯一的一条边。
性质3： 树上的所有点到其最远端的路径，一定交汇于树的中心。树的所有直径一定交汇于中心。
性质4： 树的中心做根节点时，从树的中心出发的最长链与次长链构成树的直径。
性质5： 叶子节点加一条边或删一条边，树的中心至多偏移一个点。
树的重心
此处只收录一些比较冷门的性质：
冷门性质一
等价表达：重心的子树内一定包含 dfs 序排行 $\lceil \dfrac{n}{2} \rceil$ 的点。
例题：
- [P5666](https://www.luogu.com.cn/problem/P5666)
## 树上点到链的距离公式
设 $d$ 表示节点 $u$ 到链 $(x, y)$ 的距离：
- $d = dis[u] - dis[\operatorname{LCA}(x, u)] - dis[\operatorname{LCA}(y, u)] + dis[\operatorname{LCA}(x, y)]$.
其中，$dis[u]$ 表示 $u$ 到根节点的距离。
例题：
- [HDU-5296](https://vjudge.net/problem/HDU-5296)
- [P1099](https://www.luogu.com.cn/problem/P1099)
## 并查集的运用
详见 [OI-Wiki](https://oi-wiki.org/topic/dsu-app/)。
# 计数技巧
## 所有子区间贡献求和
可以利用笛卡尔树上分治或类似的方式来求解形如 $\sum\limits_{1 \le l \le r \le n} F(l, r)$ 的式子，$F(l, r)$ 的值与区间最值相关。可以通过分治到该点时让答案加上包含该点的区间数乘以该点贡献。
## 最大值与最小值之间的容斥转化
我们在计算 $\max$ 时，如果计算 $\max$ 无从下手，但是计算 $\min$ 比较容易时，可以使用一下公式：
- $\max(a, b) = a + b - \min(a, b)$。
- $\max(a, b, c) = a + b + c - \min(a, b) - \min(a, c) - \min(b, c) + \min(a, b, c)$。
具体地：
- $\max\limits_{1 \le i \le n} a_i = \sum\limits_{k=1}^n (-1)^{k+1} \sum\limits_{\substack{1 \le i_1 < \cdots < i_k \le n}} \min(a_{i_1}, \ldots, a_{i_k})$。
反之亦然。
## 异或哈希
可以利用异或的性质，将区间或可重集合中的元素异或起来，出现偶数次的将相互抵消，奇数次的将对哈希值产生贡献。
例如要求满足区间中只有 $x$ 的出现次数为奇数次，其它元素的出现次数为 $0$ 或偶数次，我们给每个值随机一个权值 $f(x)$，设 $\operatorname{S}(n) = \oplus_{i = 1} ^ n f(a_i)$，那么题意就转化为求有多少个 $[l, r]$ 满足 $\operatorname{S}(r) \operatorname{xor} \operatorname{S}(l - 1) = f(x)$，就可以固定 $r$ 求满足条件的 $l$ 的数量，也就是求有多少个 $l$ 满足 $\operatorname{S}(l - 1) = f(x) \oplus \operatorname{S}(r)$。
例题：
- [P8819 ~~不可以！总司令~~](https://www.luogu.com.cn/problem/P8819)
- [P10833](https://www.luogu.com.cn/problem/P10833)
## 必要条件缩小枚举范围
有的时候，目标答案由于限制过多难以统计，但是答案本身的数量不多，我们可以通过削弱限制来枚举所有可能的答案，及枚举满足必要条件的答案再逐个 check。
设满足必要条件的可能答案的个数为 $n$，对于每个可能答案的 check 是 $\operatorname{O}(m)$ 的，则总体时间复杂度为 $\operatorname{O}(nm)$，通常情况下要么 $n$ 非常小，要么 check 的时间复杂度可以做到 $\operatorname{O}(1)$ 或者 $\operatorname{O}(\log n)$。
例题：
- [P10833](https://www.luogu.com.cn/problem/P10833)
- [CF1175F](https://codeforces.com/problemset/problem/1175/F)
# 字符串算法
## 进制哈希的运用
### 子段哈希值
子段 $S[l : r]$ 的哈希值为 $\operatorname{H}(r) - \operatorname{H}(l - 1) \times base ^ {r - l + 1}$，其中 $\operatorname{H}(x)$ 表示字段 $S[1 : x]$ 的哈希值。
例题：
- [P8023](https://www.luogu.com.cn/problem/P8023)
- [P3823](https://www.luogu.com.cn/problem/P3823)
## 括号匹配
### 合法括号匹配的充要条件
- 长度为偶数（废话）。
- 左括号的数量等于右括号的数量。
- 任意一段前缀的左括号数量大于等于右括号数量。
例题：
- [at_abc428_c](https://atcoder.jp/contests/abc428/tasks/abc428_c)
# 数据结构
## 0-1 trie 的运用
### 维护全局加一及异或和
#### pushup:
考虑从低位往高位建立 trie 树，每个节点维护的是子树（不包括自身）的异或和，我们规定：
- ``w[p]`` 当前节点的权值。
- ``val[p]`` 当前节点子树（不包括自身）的异或和。
每次插入将路径上经过的节点权值加一（因为只关心奇偶性，异或也可），调用 ``pushup`` 实时更新即可，代码如下：
```cpp
inline void pushup (int p) {
w[p] = val[p] = 0;
if (son[p][0]) w[p] ^= w[son[p][0]], val[p] ^= val[son[p][0]] << 1;
if (son[p][1]) w[p] ^= w[son[p][1]], val[p] ^= val[son[p][1]] << 1 | w[son[p][1]];
}
void insert (int &p, int x, int dep) {
if (!p) p = ++idx;
if (dep > K) return w[p] ^= 1, void();
insert(son[p][x & 1], x >> 1, dep + 1), pushup(p);
}
```
#### 全局加一：
考虑全局加一的实质是从低位到高位找到第一个零，将之前全部的一置为零，将这个零置为一，使用递归在 trie 树上模拟这一过程的代码如下：
```cpp
void add (int p) {
swap(son[p][0], son[p][1]);//0->1, 1->0
if (son[p][0]) add(son[p][0]);//依然存在下一位是一，递归修改
pushup(p);
}
```
例题：
- [P6623](https://www.luogu.com.cn/problem/P6623)
## 动态开点线段树节点回收
这一技巧往往运用在线段树合并当中。
重所周知，线段树合并的空间复杂度往往是 $\operatorname{O}(n \log n)$ 的，有时数据范围不允许这个大小的做法通过，此时你可以在离线查询的基础上，把之前一些对后续查询没用的节点删去，一般在合并时这么做。
开一个栈来存储删除的节点即可。
获取新节点：
```cpp
#define getnode() (top ? stk[top--] : ++idx)
```
删除当前节点：
```cpp
#define remove(u) (lc[u] = rc[u] = sum[u] = 0, stk[++top] = u)
```
~~卡常卡过一道题会有一种别样的成就感。~~
例题：
- [P5384](https://www.luogu.com.cn/problem/P5384)
## 通过 dfs 序遍历子树
这个 trick 时常运用在 dsu on tree 上。
在做 dsu on tree 的时候，经常要递归遍历轻儿子的子树获取答案或删除，常数巨大。
此时可以通过 dfs 序遍历子树，具体代码如下：
```cpp
for (auto [v, w] : e[u]) if (v != fa && v != son[u]) {
for (int i = 0, t; i < sz[v]; i++) {
t = key[dfn[v] + i];
//do something
}
for (int i = 0, t; i < sz[v]; i++) modify(key[dfn[v] + i], 1);
}
```
同理我们也可以使用拓扑序遍历一张 DAG。
例题：
- [P4149](https://www.luogu.com.cn/problem/P4149)