专栏文章

《信息学奥赛 trick 杂录》

CChiesl
个人记录参与者 3已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@minseqvf
此快照首次捕获于
2025/12/02 07:35
3 个月前
此快照最后确认于
2025/12/02 07:35
3 个月前
查看原文
持续更新ing...
欢迎各位在评论区分享经验，如若收录本文，我将注明贡献。
近七日更新：
无。

目录

Part 1. 动态规划

  • 连续段 DP

Part 2. 分治与离线

  • 树链分块

Part 3. 图论

  • 树的中心
  • 树的重心（猎奇性质）
  • 树上点到链的距离公式
  • 并查集的运用

Part 4. 计数技巧

  • 所有子区间贡献求和（贡献与最大值最小值相关）
  • 最大值与最小值之间的容斥转化
  • 异或哈希
  • 必要条件缩小枚举范围

Part 5. 字符串算法

  • 进制哈希的运用
  • 括号匹配

Part 6. 数据结构

  • 0-1 trie 的运用
  • 动态开点线段树节点回收（卡常技巧）
  • 通过 dfn 序遍历子树（卡常技巧）

引言

在信息学奥赛中，解决难题离不开日常的练习，而日常的练习如何积累成考场的思路，就要看平时对于经典 trick 的积累。

动态规划

连续段 DP

这个DP主要用于解决类似于“在一个数列中产生一个个连续块，求可能数”的动规问题。
比如，在一排连续的盒子中放苹果，连着的苹果都可视作一个连续块。
一般来说，我们都会考虑新加入的元素对原状态的影响。通常的，有三种情况：
  • 加入的元素在原先某个连续段的两端。
  • 加入的元素单独成为一个连续段。
  • 加入的元素把两个连续段连成了一个。
值得注意的是，通常不考虑连续段的具体状态，而只考虑整体状态，如连续块数量与元素数量。
这里有一篇博客讲的非常好，刚刚的介绍也摘自这篇博客，%%%。
这里直接上例题，这里有这样一个问题。
刚刚的问题是模板题，如果报名了梦熊的炼石计划NOIP的话，你将在模拟考9中遇到一个相当困难的题目，与 P7967 做法几乎一致。
例题：

分治与离线

树链分块

适用于将问题建模后为在树上向根节点跳的问题，对于每个 ii 维护跳出块所需的步数 fif_i 和跳出去以后所在的位置 gig_i，本质上是暴力。
对于部分动态树可以解决的问题，可以用这个 trick 来水过。
例题：

图论

树的中心

与树的重心不同，我们在解题时可以将直径问题转化为中心问题，以下将给出树的中心的定义与性质：
定义1： 以该点为根出发的所有路径的最长路最短。
定义2： 当一棵树以点 xx 为根时，树的高度（深度）最小，则称 xx 为树的中心。
性质1： 直径长度为偶数时，树的中心是唯一的一个点；
性质2： 直径长度为奇数时，树的中心是 一定相邻 的两个点，也可看作是唯一的一条边。
性质3： 树上的所有点到其最远端的路径，一定交汇于树的中心。树的所有直径一定交汇于中心。
性质4： 树的中心做根节点时，从树的中心出发的最长链与次长链构成树的直径。
性质5： 叶子节点加一条边或删一条边，树的中心至多偏移一个点。

树的重心

此处只收录一些比较冷门的性质：

冷门性质一

nn 个节点的树，以 任意 节点为根的 任意 dfs 序下排行 ⌈n2⌉\lceil \dfrac{n}{2} \rceil 的点的祖先链中 一定包含 重心。
等价表达：重心的子树内一定包含 dfs 序排行 ⌈n2⌉\lceil \dfrac{n}{2} \rceil 的点。
例题：

树上点到链的距离公式

设 dd 表示节点 uu 到链 (x,y)(x, y) 的距离：
  • d=dis[u]−dis[LCA⁡(x,u)]−dis[LCA⁡(y,u)]+dis[LCA⁡(x,y)]d = dis[u] - dis[\operatorname{LCA}(x, u)] - dis[\operatorname{LCA}(y, u)] + dis[\operatorname{LCA}(x, y)].
其中，dis[u]dis[u] 表示 uu 到根节点的距离。
例题：

并查集的运用

详见 OI-Wiki。

计数技巧

所有子区间贡献求和

可以利用笛卡尔树上分治或类似的方式来求解形如 ∑1≤l≤r≤nF(l,r)\sum\limits_{1 \le l \le r \le n} F(l, r) 的式子，F(l,r)F(l, r) 的值与区间最值相关。可以通过分治到该点时让答案加上包含该点的区间数乘以该点贡献。

最大值与最小值之间的容斥转化

我们在计算 max⁡\max 时，如果计算 max⁡\max 无从下手，但是计算 min⁡\min 比较容易时，可以使用一下公式：
  • max⁡(a,b)=a+b−min⁡(a,b)\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(a, b, c) = a + b + c - \min(a, b) - \min(a, c) - \min(b, c) + \min(a, b, c)。
具体地：
  • max⁡1≤i≤nai=∑k=1n(−1)k+1∑1≤i1<⋯<ik≤nmin⁡(ai1,…,aik)\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})。
反之亦然。

异或哈希

可以利用异或的性质，将区间或可重集合中的元素异或起来，出现偶数次的将相互抵消，奇数次的将对哈希值产生贡献。
例如要求满足区间中只有 xx 的出现次数为奇数次，其它元素的出现次数为 00 或偶数次，我们给每个值随机一个权值 f(x)f(x)，设 S⁡(n)=⊕i=1nf(ai)\operatorname{S}(n) = \oplus_{i = 1} ^ n f(a_i)，那么题意就转化为求有多少个 [l,r][l, r] 满足 S⁡(r)xor⁡S⁡(l−1)=f(x)\operatorname{S}(r) \operatorname{xor} \operatorname{S}(l - 1) = f(x)，就可以固定 rr 求满足条件的 ll 的数量，也就是求有多少个 ll 满足 S⁡(l−1)=f(x)⊕S⁡(r)\operatorname{S}(l - 1) = f(x) \oplus \operatorname{S}(r)。
例题：

必要条件缩小枚举范围

有的时候，目标答案由于限制过多难以统计，但是答案本身的数量不多，我们可以通过削弱限制来枚举所有可能的答案，及枚举满足必要条件的答案再逐个 check。
设满足必要条件的可能答案的个数为 nn，对于每个可能答案的 check 是 O⁡(m)\operatorname{O}(m) 的，则总体时间复杂度为 O⁡(nm)\operatorname{O}(nm)，通常情况下要么 nn 非常小，要么 check 的时间复杂度可以做到 O⁡(1)\operatorname{O}(1) 或者 O⁡(log⁡n)\operatorname{O}(\log n)。
例题：

字符串算法

进制哈希的运用

子段哈希值

子段 S[l:r]S[l : r] 的哈希值为 H⁡(r)−H⁡(l−1)×baser−l+1\operatorname{H}(r) - \operatorname{H}(l - 1) \times base ^ {r - l + 1}，其中 H⁡(x)\operatorname{H}(x) 表示字段 S[1:x]S[1 : x] 的哈希值。
例题：

括号匹配

合法括号匹配的充要条件

  • 长度为偶数（废话）。
  • 左括号的数量等于右括号的数量。
  • 任意一段前缀的左括号数量大于等于右括号数量。
例题：

数据结构

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);
	}
例题：

动态开点线段树节点回收

这一技巧往往运用在线段树合并当中。
重所周知，线段树合并的空间复杂度往往是 O⁡(nlog⁡n)\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)
卡常卡过一道题会有一种别样的成就感。
例题：

通过 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。
例题：

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...