Trick 集合

小木虫 · 2023-10-09 11:23:41 · 个人记录

大概会分个类...
2023.10.9 开始写的，之前的一些好玩的技巧会慢慢补。

图论类

1.树上最远点对

记 \text{diam}(S) 为树上点集 S 的最远点对，则有：

2.有限制的集合分组

我们可能会遇到一类问题，它要求你把一堆元素分成两个集合，而集合内部的元素两两之间有限制，则我们可以将两个放在一起会导致非法的元素之间连边，然后检查是否为二分图，这个技巧可能会和二分一起使用以得到最优化的效果。

例题：CF1849F XOR Partition

3.一般图的最大独立集/最小覆盖集

显然这个问题是一个 NPC 问题，但是我们仍有比爆搜更加优秀的算法。
考虑 \text{meet in the middle}，我们枚举前 \frac{n}{2} 个点是否选择，然后我们可以对后 \frac{n}{2} 个点进行记忆化搜索，这样做的复杂度是 O(2^{\frac{n}{2}}) 的。

例题：CF1767E Algebra Flash

4.正则图的完美匹配

若我们有一个二分图，每一个左侧节点出度为 k，每一个右侧节点入度为 k，则我们称该二分图为 k-正则图，对于任何一个这样的图，其最大匹配一定为完美匹配，证明采用反证法。

例题：[AGC037D] Sorting a Grid

数论/数学类

1.哥德巴赫猜想

任何一个大于 2 的偶数都可以被拆成两个质数之和。
感觉没什么好说的，在数论构造中会用到。
如果我们要把一个数 n 拆成尽量少的质数的和，则我们有以下选择：
1.若 n 本身为质数，则自己就是方案。
2.若 n 为偶数，根据结论可知我们可以 O(n) 地找到一种拆成两个质数的方法。
3.若 n 为非质奇数，我们要么将其 -2 获得一个质数，此时用两个质数，我们要么将其 -3 获得一个偶数，然后再按上述方法找到方案，此时方案为用三个质数。

例题：CF45G Prime Problem

对于一类比率问题的通用解法

有些题目可能会给定一个比率 \alpha，然后要求最小的 n 使得：

其中 w 为一个条件表达式，代表下标 i 所代表的元素满不满足一个条件。
当题目保证此问题有至少一个解的时候，我们可以尝试如下算法。

1.定义目前的答案 n=1。
2.算出最小的 x ，使得 \dfrac{x+\sum_{i=1}^n [w(i)]}{x+n}\geq \alpha。
3.将 n 更新为 n+x，检查此时是否满足题目条件，若满足则此时的 n 为答案，否则返回步骤 2 进行下一轮迭代。

可以证明，此种迭代法的复杂度是仅与精度相关的，当计算精度为常数时此种方法的迭代复杂度也为 O(1)，当然，常数较大，一般来说在 100 以内。

n 阶前缀和中原始元素在最后一个元素中的出现次数

例题：[ARC137D] Prefix XORs

贪心/DP类

1.交换维度与权值

当 DP 的权值很小但是维度较大时可以尝试进行它们的交换，即 DP 在这个权值时最优的维度值是多少，具体可参考 [AGC033D] Complexity 。

2.稠密图的最大流转最小割

有部分题目我们直接建出来的最大流模型的边数非常多，同时这个图可能有一些特殊性质，如这是一个二分图，此时我们可以考虑将最大流转化成最小割，然后使用 DP 或贪心来维护最小割，避免遍历每一条边。

例题：[ARC125E] Snack ，CF724EGoods transportation

3.计数转期望

对于某些题目，它要求你计数的内容是非常难以设置状态的，这种情况下我们只能对于每一个元素求贡献，此时可以使用期望的线性性（期望的和等于和的期望）来对题目进行转化（每个元素做出贡献的期望），然后我们把每个地方的贡献加起来就是我们要求的答案的期望了。

例题：[AGC030D] Inversion Sum

4.区间最小点覆盖问题

给定 n 条线段，要求在数轴上撒若干点，使得每一条线段内至少有一个点，问最小撒点数量。
很经典的贪心问题。
解法：将线段按右端点从小到大排序，若当前线段内已经包含点则跳过，否则选择该线段的右端点。
证明：按右端点排序后每一个选择的线段都是两两不交的，则至少要选这么多点。

化归：区间最多独立区间问题。
若几个区间能被同一个点覆盖则说明他们相交了。
有几个点就有几个独立区间，两者本质相同。

例题：CF1841D Pairs of Segments

数据结构类

1.序列上启发式分裂

给定一个排列 p，我们可能会需要对每一个元素算贡献，当这个元素为区间内的最大值或最小值时它会有贡献，那么此时我们可以用单调栈求出其为最值的区间左边界和右边界。
然后我们类似平凡分治地，考虑该元素的一边向另一边做贡献，我们显然需要枚举一边，这看似不可接受，但我们只需要枚举大小更小的一边，则我们枚举的复杂度则为均摊 O(n\log n) 的，证明其实很好证，但是如果没见过这个 trick 的话一下想到还是很难的。

例题：CF1849E Max to the Right of Min

杂项

1.区间内的异或方程的解集

对于任意正整数 x，若 x \oplus y = k 且 L\leq k \leq R。
则满足条件的 y 会形成 \log V 个区间，具体操作可以按位考虑，先只把 k\leq R 的部分写出来，这是容易的，然后去除 k<L 的部分。

例题：CF1849F XOR Partition

2.序列的两两异或最小值

一个很直觉，证明也非常简单的 trick，但是如果你提前见过这个 trick 你可能使用起来会更加得心应手。
给定一个序列 a，求 \min_{1\leq i < j \leq n}a_i \oplus a_j。
你可以直接将 a 排序后，所有相邻元素的异或值的最小值即为答案。
证明你直接放到 01trie 上证。

3.不合法方案转更劣方案

有时你并不能限制一个方案必须合法，这样做的复杂度过于高了。
但是你也许可以将这个方案变为一个一定劣于最优方案的方案。
具体的实例有拆绝对值，钦定前 k 大后可能不会真的有 k 个这么大的元素，于是我们强制将更小的值补齐上去。
直接说很抽象，直接放例题：
P6961 [NEERC2017] Journey from Petersburg to Moscow ，CF1859E Maximum Monogonosity

4.对特殊区间进行异或卷积的特点

若我们有形如 [k\times a^b,(k+1)\times a^b) 的区间。

则对于任意两个这样的区间，他们进行异或卷积后的新区间仍然是连续，且依旧满足此特性的。

对于任意一个区间，我们可以将其挂在一个满线段树上拆出 \log V 个满足上述条件的区间，a=2。

预留位

感觉还有好多题和技巧没有说啊...
等我想补了再说吧。