套路

· · 算法·理论

计算几何

1. 求凸包的交

给出两个凸包，求它们的交（即同时被两个凸包包含）。

将每个凸包拆成一些半平面的交，再把两个凸包的所有半平面全都交起来。

例题：不知道

2. 平面凸包计数

平面中有若干个点，问其中一些点构成凸包的方案数。

思路参考 CF1146H。

凸包上的边按顺序一定是斜率递增的，于是将 n^2 条线段先按照斜率排序。

接下来考虑 dp，f_{i,j,k} 表示从点 i 经过 k 条边到达点 j 的方案数。

则按照顺序更新每条线段，对于点 u 到点 v 的线段有如下转移：

\forall i,j,\quad f_{i,v,j}\gets f_{i,v,j}+f_{i,u,j-1}

边界为 f_{i,i,0}=1，答案为所有的 f_{i,i,j} 的和。

例题：CF1146H

3. 最小乘积模型

对于一个不知道什么问题，如果每个方案有两种权值，最后要求最小化两种权值之积，可以考虑放到坐标系上。

容易发现 xy 最小的点一定在点集构成的凸包上。考虑找出最靠左和最靠下的两个点，之后每次分治找到离当前直线最远的点（且靠左），然后继续做下去。

离当前直线最远的点可以转化成叉积最小从而将问题转化成普通的单权值最小化问题。

例题：P6158，P5540，P3236

字符串

1. 后缀 LCP

对于一个字符串 s，求 \sum\limits_{i=1}^{|s|}\sum\limits_{j=i+1}^{|s|}\text{LCP}(suf_i,suf_j)，其中 suf_i 表示以 i 开头的后缀。

典中典。首先建出后缀数组和 height 数组，则问题转化为 \sum\limits_{i=1}^{|s|}\sum\limits_{j=i+1}^{|s|}\min\limits_{k=i+1}^j height_k。

然后就转化为了经典问题。但是我忘了咋做了，呜呜。

好像可以通过分治做到 O(n\log n)，忘了有没有更优做法了，反正基本不会有人卡这个把。 可以单调栈做到 O(n)，我是不是唐氏。

例题：一堆。

2. 同构子串

给出两个字符串 s 和 t，问 t 中有多少个与 s 同构的子串。

哈希，每个位置记录的是上一个与当前字符相同的位置与当前位置的距离，这样同构的子串对应哈希值就相等了。

维护的时候需要支持修改之前某一位的哈希值。

例题：一堆。

3. 本质不同回文子串

本质不同的回文子串只有 O(n) 个。

证明：对于每个 i，以它结尾的之前没出现过的回文子串最多只有一个。因为考虑最长的那个回文串，其余所有比它短的以 i 结尾的串都可以通过在大回文串上面翻过去来移到之前一个我们已经找到过的串上面。

例题：回文自动机，Manacher。

网络流

1. 拆边

对于一些费用流中的特殊边权，如果边权为关于流量的函数且这个函数是下凸的，那么可以通过将这条边拆成非常多条边权为 1 费用依次为 f(1),f(2)-f(1),f(3)-f(2),\dots 的边来解决这个问题。

例题：P4249

2. 平面图最小割转对偶图最短路

典。

例题：P4001

博弈论

1. 树上删边博弈

见 AT_agc017_d。

2. DAG 博弈

DAG 博弈中，如果把所有 SG=0 的点全都删掉，剩下的点的 SG 是原来的 SG -1。

例题：AT_agc016_f

3. k 倍取石子游戏

见 UVA1567。

4. 翻硬币博弈

对于那些“两人轮流每次选择一些硬币（可能有一定限制）翻转，其中要求最左侧或者最右侧的硬币必须为正面朝上，不能操作者输”的博弈问题，能够证明各个硬币之间的贡献是独立的，即 SG(P)=\bigoplus_i S_i，其中 S_i 表示只有第 i 位为 1 时的 SG 值。

例如如下问题：每次选择三个位置 l,m,r 满足 r 位置正面朝上并翻转这三个位置的硬币，不能操作者输。

证明：

例题：P3179

DS

1. 区间 +1/-1 变为同一个数的最小次数

真不会取名了

对于一个序列，每次操作可以让一段区间同时 +1 或 -1，求整个序列全都变为 v 的最小操作次数。

容易发现同时 +1 或 -1 对应的差分数组恰好是一个 +1 和一个 -1。

首先在序列两端都插入 v。对于接下来的差分数组，因为开头和结尾都是同一个数，那么肯定差分数组的和为 0，而我们现在的目标就是把整个差分数组都变为 0。

容易发现每次修改一定是让两个位置的绝对值都 -1，所以答案至少为 \frac{\sum |d_i|}2。

而因为差分数组的和为 0，所以一定可以构造出一种方案使得恰好用最少的操作次数把差分数组归零。我不会证明。

例题：P4552

2. mex 矩形

如果将区间 [l,r] 视作平面上的一个点，点的颜色是这个区间的 \text{mex}，那么这个平面有 O(n) 个矩形构成。

例题：P9970，CF1148H，P10169

3. 直角三角形信息

遇到形如 \max\limits_{i+j\le x}a_i+b_j 的问题可以考虑用 a 和 b 的下标建立直角坐标系，这样问题相当于求一个直角三角形形状中的答案。将这个直角三角形分成中间的长方形和两边的两个小直角三角形，容易发现这个东西和线段树的分治结构相同，因此用线段树维护。

例题：P6780，P9877，P6717

4. Trie 的一种用法

如果有问题需要一种数据结构支持全局 +1，插入一个数，一些全局的需要按位处理的操作以及查询，可以考虑把所有数从低位到高位建 trie，对于全局 +1 考虑先将根的所有儿子进行一个轮换（0\to 1,1\to 2,\dots,base-1\to 0），之后整个 0 的子树内还要继续进位，所以继续递归下去做即可。

例题：AT_agc044_c，CF1511G，P6623

5. 总修改量巨大但是有效修改极少

如果你需要维护一个序列上的东西，在维护的时候会有非常多范围很大的修改，但是每个位置对应的值的总变化量并不是很大的话，假设这个总变化量为 c，操作次数为 m，那么用树状数组维护区间的哈希值，每次二分到下一个需要变化的位置然后直接修改，总时间复杂度 O(c\log n+m\log^2 n)。

例题：Gym103428C

6. 换维扫描线

典。

例题：QOJ8229，QOJ971

图论

1. 树上点集直径

对于两个点集 A 和 B，假设它们的直径端点分别为 x_A，y_A，x_B，y_B，那么 A\cup B 的直径端点一定在这四个点中。

例题：P2056

2. 神秘欧拉回路套路

对于任意一张无向图，我们可以给每条边定向使得 \forall v,|indeg(v)-outdeg(v)|\le 1。

证明：显然一定有偶数个度数为奇数的点。将它们两两分组，每一组的两个点连一条边，这样所有点就都是偶点了，于是新图一定有欧拉回路。按照欧拉回路的方向定向后去掉添加的边，这样每个点的入度或出度最多变化 1，满足上面的条件。

例题：P8326，Gym102893G

3. 分层图

遇到一些图论相关问题但是有一些神秘的和 \bmod 有关的限制时，可以考虑将图复制成若干份用来表示模意义下的不同结果。

我已经被这个套路卡过三次了

例题：P9370，P9751

4. 边转点

遇到一些奇怪的边权上的问题可以尝试转化到点权上。

例题：？

5. 动态加边维护强连通性

对于有向图动态加边维护强连通性，可以先离线下来，通过整体二分求出每条边什么时候进入一个强连通分量，从而将强连通性问题转化为连通性问题。

例题：P5163，QOJ2214

6. 点减边容斥

对于一些树上数据结构题中限制点集连通时求答案的时候，可以通过点减边容斥转化为所有情况中 |V|-|E| 的最小值以及对应权值的和，然后再进行数据结构的优化。

例题：P8990

其它

1. Thue-Morse 序列

OEIS A010060

这里 a_i=popcount(i)\bmod 2。

那么会有一个特殊性质：将 0\sim 2^n-1 按照 a_i=0 和 a_i=1 分组，则两组的任意次方之和都相等。

证明可以参考 这个。

此外还有 一种扩展。

这个套路比较经典，有几个类似题目：

2. 高维空间超平面分割的方案数

在 k 维空间中，用 n 个 k-1 维超平面最多可以把空间分成多少部分？

答案是 (^n_0)+(^n_1)+\dots+(^n_k)。

证明可以看 这个。

例题：不知道

3. 高维前缀和及其扩展

对于一些各维度之间贡献独立的问题，可以先考虑枚举维度，在每一个维度内部直接计算完这一维对每个数造成的贡献。

例子：FMT，狄利克雷前缀和，AT_abc288_G

4. 神秘 poly 套路

如果有的多项式函数比较复杂难以计算，可以考虑计算出非常多个点值再拉插回去。

例题：P4365，AT_arc118_f

5. 线性基的炫酷性质

对于数组 a_1\sim a_n 考虑其线性基 p_i=\bigoplus\limits_{j}a_{id_{i,j}}。

令 b_i=b_{i-1}\oplus a_i（即 a_i 的前缀异或和），可以发现 p_i'=\bigoplus\limits_{j}b_{id_{i,j}} 为 b 的线性基（即下标集合完全相同）。

例题：AT_arc145_e

6. Shopping Plans' Tirck

Link

例题见上。

7. 原根最有用的一集

在模数 P 比较小可以进行 O(P) 预处理且问题涉及到乘法相关时可以通过将所有数转化为原根的幂从而将乘法化为加法。这样可以做到 O(1) 快速幂。

例题：P11175

8. Dilworth 定理在其他方面的应用

有很多常见的偏序关系往往不被大家在意，所以在这些地方所蕴藏的 Dilworth 定理有时反而难以发现。

e.g.：一个序列的最长上升子序列长度不超过 k 等价于这个序列可以被划分为 k 个不升子序列。

例题：P4769，AT_arc068_d，P11231

9. 01 串相邻项操作可以考虑对奇（偶）数位取反

如题，这样可以将问题进行一些化简，例如：

例题：AT_tkppc6_2_b，QOJ9565，P10068，AT_agc040_c

10. 对指定 \max 或 \min 的折线图计数

考虑如下问题：对所有长度为 n，每一项为 +1 或 -1，前缀和的 \max=k 的序列计数。

正着 dp 需要记三维：当前位置，目前的 \max，目前的前缀和。

但是考虑倒过来 dp，每次在当前折线的最前面插入一项，这样 \max 的变化是好处理的，于是就变为 O(n^2)。

例题：P14256

11. 系数等用到了再算，没用到的东西不区分

在进行一些计数的 dp 中，我们可能会遇到一些情况需要在后面的状态中随机选择一部分进行变化。

如果我们直接记录它们具体的变化情况，那么状态数将无法承受。于是我们在从前往后 dp 的过程中记录一下后面有多少次操作还没有分配，转移的时候枚举当前位置分配走了多少次操作，而后面的状态不提前分配，正确性显然。

例题：CF1842G，P14364

12. 转 01

遇到各种排列或者序列上需要比较值的大小的问题（例如排序，取 \min 或 \max 等）可以考虑对于每个 k 把序列 p_i 变成 [p_i\ge k]，这样对于每个 01 序列分别处理最终再合起来可能能够化简问题。

例：

  1. 可以将一些排列上的最优化问题拆开到每一位计算独立贡献从而方便计数
  2. 通过将排列转化为一条从 (0,0,\dots,0) 走到 (1,1,\dots,1) 的路径来把维护排列的问题转化到维护每一个 01 序列

例题：P7324，AT_arc160_f，QOJ12153，P10813