2023-07-10

UOJ Round #19

A. 清扫银河

$n \le 30, m \le 100$

暴力枚举所有操作。

$n \le 100, m \le 500$

找出原图生成森林，每条非树边均形成一个环。

不难证明所有的简单环均可以通过若干次非树边形成的环异或得到。

将操作 2 拆成若干次单点操作，如果一条边的两个端点均被操作或均未操作则颜色不变，否则颜色改变。

有用的操作种数至多为 $m + 1$，使用高斯消元求解异或方程组，判断是否有解。

时间复杂度 $\mathcal O(\frac{T m^3}{w})$。

$n \le 300, m \le 44985$

称所有颜色为 1 的边形成的子图为目标子图，若目标子图中所有节点度数均为偶数，则可以通过 $m - n + 1$ 次操作得到一组解。

由于多次操作 2 总可以合并至一次进行，因此至多进行一次操作 2，总操作次数为 $m - n + 2 \le m + 1$。

时间复杂度 $\mathcal O(\frac{T n^3}{w})$。

$n \le 10$
$a \le 10$

记录每种数字出现的次数。

时间复杂度 $\mathcal O(\binom{2 n}{n} n)$。

$n, q \le 5 \times 10^3$

暴力模拟。

时间复杂度 $\mathcal O(n^2)$。

$n, q \le 1 \times 10^5$

分块。

时间复杂度 $\mathcal O(n \sqrt{n \log n})$。

$n \le 5 \times 10^5$

线段树维护后缀最小值。

时间复杂度 $\mathcal O(n \log^2 n)$。