随机化算法 ​

爬山法 ​

适用范围：

• 处理有平台的单峰函数最值
• 平台不能太长

但是随机次数要多一点。

color coding ​

适用范围：

• 刻画解集中至少有多少种颜色数的限制
• 不同颜色数不太大

实现： 给每个原颜色随机一个 $0$ ~ $k-1$ 的新颜色。 其中，$k$ 需要调参，使得正确率和复杂度达到平衡。

例题：

• THUSC 巧克力
• CF2003F - Turtle and Three Sequences
• CF1641D

随机集合法 ​

适用范围： 刻画特殊的全称命题。

实现： 随机取全集的若干个子集，对于子集进行判定。

例题：

• CF1746F
• NOI2013 向量内积

行列式刻画法 ​

适用范围： 刻画解集中的两两颜色不同的限制。

实现： 假如要求一个大小为 $k$ 的两两颜色不同的解集。 那么，给每一个颜色随一个 $k$ 维向量。 钦定一个解集的权值为其向量拼接的行列式的值。

注意，如果是解集是有序集，还需要乘上一些系数，防止不同排列的行列式值相同或相反。 一种系数是每一条边赋权，最后取乘积。

计算行列式的值可以状压。

构造方案： 每次取出一个必定是合法解集中的末尾的点，将其删去，然后重复做就可以了。 注意保证当前删去的点可以转移到上一次删去的点。