ICPC 2023 澳门区域赛（Macau Regional）部分题解

Wallbreaker5th大约 2 分钟

A. (-1,1)-Sumplete

给定一个 $n \times n$ 的矩阵，每个位置上为 $-1$ 或 $1$ 。你要保留一部分格子，使得每行、每列的和等于给定的值。构造任意一种方案。 $n\leq 4000$ 。

首先保留所有 -1 而去掉所有 1。这样每个格子都可以更改其选择，使其加一。每行/列都会要求比初始方案多一定的值。

枚举每一行，选择那些当前缺 +1 最多的列，在这些格子上加一。

给定一个图，每个点的度数不超过 3，每条边有红色、蓝色。求其导出子图的个数，满足其仅通过红色边连通、且仅通过蓝色边连通。 $n\leq 10^5$ 。

首先注意到满足条件的导出子图至多有 4 个点（否则边的数量太大），并且红色、蓝色边各会形成一条链。

直接搜索找到所有红/蓝色边构成的、长度不超过 4 的链，比较这些链的点集，如果一个红色链和一个蓝色链的点集相同，那么这个点集就是一个满足条件的导出子图。

需要一些技巧来加速搜索，比如记录来源点、不搜索单个颜色度数为 3 的点。

给定若干个由直线定义的半平面，对其进行并、交、非、对称差的运算，求最终的区域（交上边界矩形框）的面积。 $n\leq 300$ 。

这些直线会将整个平面分成 $O(n^2)$ 个小块，每个小块都可以求出面积，并验证其是否在最终的区域内。并且这些小块的边数之和也是 $O(n^2)$ 的。

于是直接搜索，考虑对于每条直线取其内侧还是外侧；每加一条直线，如果当前区域的面积已经为 0，则剪枝。