===== A. Circle Coloring ===== 签到题。 ===== B. Arrays Sum ===== 不 FST 就是签到题。 ===== C. Discrete Acceleration ===== 签到题。 ===== D. Searchlights ===== 签到题。 ===== E. Avoid Rainbow Cycles ===== **题目大意**：给你 $m$ 个集合，每个集合有若干 $1\sim n$ 的元素，删除某个元素需要耗费一定的代价。删除后，对第 $i$ 个集合中的元素，两两连一条颜色为 $i$ 的边。要求该图中不存在一个环使得环中所有边颜色相同。求最小代价。 **题解**：将集合编号 $i$ 和其中的元素 $j$ 连边，得到一个二分图。注意到一个环同时也是二分图中的一个环，那么显然需要求二分图的一棵最大生成森林。 ===== F. Two Different ===== **题目大意**：设有函数 $f: \mathbb{N}\times\mathbb{N}\to\mathbb{N}$。给你一个长度为 $n\le1.5\times10^{4}$ 的数列 $a_{i}=i$，允许进行 $q\le5\times10^{5}$ 次操作，每次操作选择下标 $x,y$，令 $a_{x}:=a_{y}:=f(x,y)$。要求给出一个操作序列，对于任意的 $f$ 均可使得操作完后 $a$ 数组中元素不超过 $2$ 种。 **题解**：容易发现，使用 FFT 的技巧可使一长度为 $2$ 的幂的数组变得相等，而使用 ST 表的技巧即可使得元素数量不超过 $2$。 ===== G. Clusterization Counting ===== **题目大意**：给你一个完全图，所有边的边权互异。现在将图划分成若干个团，要求每个团内部的边权严格小于它里面的点连到外面的边权。求对每个 $x$，求划分为 $x$ 个团的方案数。 **题解**：假设一个团的最大边权为 $x$，将所有 $\le x$ 的边连起来，考虑 $x$ 所在的连通块，所有的点必须包含，否则会导致非法。而其它连通块的点则不得包含，否则会导致该连通块的最大边权超过 $x$。那么只要 $x$ 所在的连通块是一个团即合法，而我们的目标是将原图划分成若干个这样的团。这个也比较简单，从小到大加边，如果两个连通块合并，乘一下 dp 数组，如果一个连通块变成了团，那么方案数加 1。 ===== H. Rainbow Triples ===== **题目大意**：给出 $n$ 个整数 $a_{1},a_{2},\cdots,a_{n}$，要求你找出 $m$ 个三元组 $\{(u_{i},v_{i},w_{i})\}$，使得 $a_{u_{i}}=a_{w_{i}}=0$，$a_{v_{i}}>0$，$u_{i}