CF1720E Misha and Paintings 题解

Daidly · 2022-08-20 09:57:43 · 题解

Codeforces Round #815 (Div. 2) 全场题解以及更好的阅读体验

记原始矩阵中不同值的个数为 m。

• m\leq k

每次只要选中一个 1\times 1 的小矩阵改变值即可，最小操作次数为 k-m。

• m>k

样例以及手玩似乎答案不超过 2？考虑证明。

我们构造出一种两次一定能解决的方案。

不妨让第一次选中的正方形左上角为原矩阵左上角，假设我们能增加长度 L 就增加，并且此矩形的颜色我们不统计上，即颜色为剩下 k 个之一，不增加颜色。

也就是说，我们选择了最大的 L 使得 m'\ge m，L 再增加 1 就会使 m'<m。

我们考虑第二个矩形，将它的右下角置于 (L+1,L+1)，向左上扩展，颜色与第一个矩形相同，都不对整体做贡献。

可以发现，每当第二个矩形边长多 1 就会多两个格子消失，最多消失两种颜色，所以可以通过此将颜色变到 k 或 k-1。

当 m'=k 时，已满足要求；当 m'=k-1 时，我们可以将第二个矩形的颜色换成一种新的颜色，将 m' 增加 1，使其等于 k。

这样我们就证明了最多两次。

我们考虑什么时候答案为 1，其余时候都为 2。

先计算出每个颜色的上界 (x1,y1)，下界 (x2,y2)。即 (x_1,y_1),(x2,y2) 是满足能覆盖此种颜色的最小子矩阵。

枚举一个正方形的边长 len，然后枚举左上角 (i,j)，记 c[i][j] 为当边长为 len 左上角为 (i,j) 时，能覆盖的颜色个数。

考虑如何计算 c[i][j]，直接算复杂度太高，考虑每个颜色的贡献。

对于一种颜色 ，通过它的上下界可以计算出在哪一个区域内的点以 len 为边长得到正方形可以覆盖这种颜色。

我们通过二维差分加二维前缀和解决 c 的计算。

最后我们只需要判断每一个点 (i,j) 在长为 len 的前提下计算出的 m-c[i][j] 是否等于 k 或 k-1 即可。