Codeforces Round #576 (Div.1)

A. MP3

除了挖坑一无是处的屑题，不写了！

B. Welfare State

题意：两种操作，全局取max，单点修改，输出最终的序列。

题解：segment beats!

C. Matching vs Independent Set

题意： $3 n$ 个点的图，找出一组大小为 $n$ 的匹配或独立集。

题解：扫描所有边，能匹配就匹配。若匹配数大于 $n$ ，输出匹配。否则剩下的点形成独立集，原因：如果有边，之前暴力扫描会被匹配到。

D. Rectangle Painting 1

题意：有 $n \times n$ 的矩形，格子是黑色或白色，每一可以花 $max {h, w}$ 的代价把 $h \times w$ 的矩阵染白，问将全体染白的最小代价。 $n \leq 50$

题解：

证明一个结论，假设不是 $n \times n$ 的矩形，而是一般化为 $n \times m$ ，不妨设 $n \geq m$ ，则有最优解一定是 $n \times m$ 全覆盖，或者存在一个垂直于 $n$ 方向的分界线，没有染白矩阵跨越这条线。

证明：如果不存在这样的线，每一处分界线都至少有一个矩形越过，容易发现这样的方案一定不优于直接全覆盖。

于是暴力地来个dp，令 $d p_{x l, x r, y l, y r}$ 为覆盖子矩形 $[x l, x r] \times [y l, y r]$ 的最小代价，选择长的那一边暴力枚举分界线，递归到左右两边求和，最后和全覆盖取更优。复杂度 $O (n^{5})$ ，小常数可以过。

E. Rectangle Painting 2

题意：有 $n \times n$ 的矩形，格子是黑色或白色，每一可以花 $min {h, w}$ 的代价把 $h \times w$ 的矩阵染白，问将全体染白的最小代价。 $n \leq 10^{9}$ ，黑色位置由 $m$ 个可以有交集的矩形给出， $m \leq 50$

题解：

首先发现一定是取宽度为 $1$ 的横向/纵向长条最优。

先离散化，于是对每一个黑格子 $(i, j)$ ，这代表了第 $i$ 行或者第 $j$ 列需要被选中，问最少选中数。

这就是个点覆盖问题，二分图上转最小割就行了。因为离散化，点是带权的。

F. GCD Groups 2

题意：有一堆数，把它们分成非空两组使 $gcd$ 均为 $1$ ，或说明方案不存在。

题解：

考场上没做出来。

假设存在一组这样的方案，不妨考虑第一个数 $a$ 所在的集合， $a$ 最多有 $k = 9$ 个质因子，对每个质因子，显见 $a$ 所在的组里至少有一个数不含这个质因子。于是 $a$ 所在的集合可以只保留这些数而 $gcd$ 仍然为 $1$ ，这些数共不超过 $k + 1$ 个。即：如有解，则一定存在 $a$ 所在的组只含至多 $k + 1$ 个数的解。

那么直接随机一个数 $b$ ，并钦点它和 $a$ 不在一个集合，钦点出错的概率至多为 $\frac{k}{n}$ ，多随机几次就几乎不会错了。

假设有一次钦点对了，那么 $b$ 也只有至多 $k$ 个质因子。添加数的时候，只需要把 $a$ 和 $b$ 的质因子消完即可。现在这样选出 $O (k^{2})$ 个数：对 $a$ 或 $b$ 的每个质因子，选出 $2 k$ 个或者所有能消去这个质因子的数，并集为 $S$ 。那么原情况有解等价于 $S \cup {a, b}$ 上有解，原因：对一种方案， $a$ 和 $b$ 都只需要其中最多 $k$ 个数，把能消去某个质因子的全部换成 $S$ 中的同样功效的数，显然仍合法。

于是只剩下 $O (k^{2})$ 个数，直接dp，用 $d p_{S, T, i}$ 表示考虑了前 $i$ 个数， $a$ 剩下质因子集合为 $S$ ， $b$ 剩下质因子集合为 $T$ 的方案是否存在，转移容易得出。复杂度 $O (4^{k} k^{2} + n k)$ 。