CF1710A题解

linyuhuai · 2022-07-25 13:56:49 · 题解

长文前往 blog 获得更好的阅读体验 & 原题链接

2023/6/14：修改部分内容。

先给下结论：

• 每种颜色必须涂满连续的两行或两列
• 根据上面的结论进一步推导出所有颜色只能竖着或横着。

证明：

• 约定：

  1. 文章中 (x,y) x 指行号，y 指列号。

  2. 文章中，设 (i,j) 的颜色为 color_{i,j}：

  • XX 颜色块的左上指所有符合条件的 (i,j) 其中 color_{i-1,j}\not=color_{i,j},color_{i,j-1}\not=color_{i,j}。

  • XX 颜色块的右上指所有符合条件的 (i,j) 其中 color_{i-1,j}\not=color_{i,j},color_{i,j+1}\not=color_{i,j}。

  • XX 颜色块的左下指所有符合条件的 (i,j) 其中 color_{i+1,j}\not=color_{i,j},color_{i,j-1}\not=color_{i,j}。

  • XX 颜色块的右上指所有符合条件的 (i,j) 其中 color_{i+1,j}\not=color_{i,j},color_{i,j+1}\not=color_{i,j}。

  • XX 颜色块的（左上/左下/右上/右下）还要求 color_{i,j}=该颜色。

  • • 注意：一个颜色块的（左上/左下/右上/右下）可能不止一个。

我们假定有两种及以上的颜色。

• 如果只涂一列：

那么显而易见每种方块只有上下两个方块与之相邻。不满足题目要求。

• 如果所涂的列都涂满了且涂了两列及以上（其中 n=8,m=5）：
• （注意其中黄色部分只是代表除蓝色以外其他颜色，不代表单一颜色）：

对于不处于边缘地区的方块，一定有上下左右四个同颜色的方块，也就是，不在边缘地区的方块不会影响答案。

对于在边缘地区不在 蓝色颜色块的左上左下右上右下 的方块，一定有除了面对黄色的方向外其他三个方向有同颜色的方格。

对于在蓝色颜色块的左上左下右上右下的块，根据题目的定义，(1,2) 和 (8,2) 也算相邻，(1,4) 和 (8,4) 也算相邻，再加上前一条的结论，那么其均有 3 种同颜色的方块与之相邻。符合题目要求。

• 如果没涂满任何一列或一行且涂两列及以上：

显而易见在蓝色颜色块的左上左下右上右下都只有 2 种同颜色的方块与它相邻。

蓝色颜色块的左下最多只有上和右两个相同颜色方块相邻。因为如果左有了相同颜色的方块，那么就不符合左下的定义。左下如果下有了同颜色的方块也不符合定义。其他 左下右上右下 区域同理。

但特别考虑 x_{左下}=n 时，此时题目定义的”下“是位于 (1,y_{左下})。但特别注意不涂满一列指的是这一列中有两种或以上颜色，不要求这一列的颜色是一个块，更简单的说就是 (1,y_{左下}) 可能与 (n,y_{左下}) 颜色相同。

但是对于这种情况我们发现 x_{左上}\not=1 （不涂满一列，如果一块中 x_{左上}=1,x_{右下}=n，那么就涂满了这一列）也就是左上的上面一块一定是 (x_{左上}-1,y_{左上})，那么根据前面的结论左上一定没有三个同颜色的相邻方块。

对于行的证明，只需要把图翻转过来即可。

但特别的，对于这种奇奇怪怪的形状：

还有

注意到结合开头的约定，第一张图有不止一个的左上左下右上右下。如左下可能在 (9,1),(4,5),(7,7),(9,8)。

在蓝色与黄色的交界处，一定存在一格颜色，且这格只有两格相同颜色相邻。上文已经对此种情况所出现的左上左下右上右下格进行证明。但如下图所示，对于蓝色可能左上左下右上右下均符合要求，但观察黄色区域，考虑黄色区域最优情况，即全部都是同一种颜色，结合前面证明，发现黄色区域并不符合要求。

证毕。

实现

前排提示：本份题解的复杂度是 \mathcal{O}(k\log k)，劣于官方题解的 \mathcal O(k)。但数据范围允许此做法通过。

结合上面的结论。

第 i 种颜色至少取 2 行或 2 列，至多取 \lfloor \frac{a_i}{m}\rfloor 行或 \lfloor \frac{a_i}{n}\rfloor 列。

我们分别把 \lfloor \frac{a_i}{m}\rfloor 和 \lfloor\frac{a_i}{n}\rfloor 分别压入两个大根堆。

我们先选取一个大根堆，不停的取里面的元素。

取到第 k 个元素时，判断该元素与前面元素加和是否大于等于对应的 n 或 m。

如是，判断 k\times2\le\ 对应的\ n\ 或\ m。（因为前面 k 个元素每个至少要 k\times2 对应的行或列）

如果 k\times2\le 对应的\ n\ 或\ m，输出 yes。

然后再选取另外一个大根堆也同样进行以上操作。

判断下来一个 yes 都没输出，那么就是 no 了（这不是废话吗）

为什么要大根堆？

因为这样我们可以在 k\times2 尽可能小的情况下选到最大的 \sum^k_{j=1}\lfloor \frac{a_i}{m}\rfloor 或 \sum^k_{j=1}\lfloor \frac{a_i}{n}\rfloor（注意 i 不是定值，i 的值变换方式取决于遍历顺序）。

代码