题解：CF1720E Misha and Paintings

· · 题解

更好的阅读体验

好题要点赞！

假设初始时矩阵中颜色总数为 m。

\boldsymbol {m \le k}

这个时候我们要多染 k - m 种颜色。由于每次操作只能染一种颜色，因此我们多染 k - m 种颜色就要多进行 k - m 次操作。所以这部分答案为 k - m。

\boldsymbol {m > k}

我们考虑一种神秘的构造。

我们以 (1, 1) 为左上角画一个边长为 len 的正方形（即图中蓝色部分）。假设现在矩阵种颜色总数为 m'，我们约定 k \le m' \le m。

接下来，我们以 (len+1, len+1) 为右下角画一个正方形，如上图种绿色部分。注意在实际操作中我们是先画绿色再画蓝色，因此绿色正方形的左上部分会被蓝色正方形覆盖，而真正染上绿色的部分是一个以 (len+1, len+1) 为直角的 L 形。

记绿色正方形边长为 len'，则 len' 每增加 1，被绿色覆盖的格子就多出来 2 个，总的颜色种类数会减少 [0, 2] 中的一个数。

因此最终随着绿色区域的不断扩展，总的颜色种类数会达到 k 或 k-1，k-1 的情况可以对矩形颜色进行调整达到 k。

至此，我们说明了这种情形下最多 2 次操作可以达成目的。

接下来考虑什么情况可以用一次操作解决。一次操作可以解决的情况，就是存在一个正方形，把只在这个正方形中出现的颜色扣掉后，总颜色种类数为 k 或 k-1。那么我们预处理出每个颜色最靠上、下、左、右的出现位置，只有正方形包含这些位置，这种颜色才能只在这个正方形中出现。

那么我们枚举正方形边长 len，我们很容易可以求出要完全覆盖一种颜色，正方形左上角应该在的区域。这个区域的形状很显然是一个矩形，我们用二维差分维护即可。

那么这道题就做完了，复杂度 O(n^3)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 506
using namespace std;
inline void chkmax(int &x,int y){x=x<y?y:x;}
inline void chkmin(int &x,int y){x=x<y?x:y;}
int n,k,m,a[N][N],t[N*N],c[N][N];
int maxx[N*N],minx[N*N],maxy[N*N],miny[N*N];
void solve()
{
    for(int i=1;i<=n*n;i++)
        maxx[i]=maxy[i]=-1e15,minx[i]=miny[i]=1e15;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            chkmax(maxx[a[i][j]],i),chkmin(minx[a[i][j]],i);
            chkmax(maxy[a[i][j]],j),chkmin(miny[a[i][j]],j);
        }
    for(int len=1;len<=n;len++)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)c[i][j]=0;
        for(int i=1;i<=n*n;i++)
        {
            if(maxx[i]<0||maxy[i]<0||minx[i]>n||miny[i]>n)continue;
            int i1=max(1ll,maxx[i]-len+1),j1=max(1ll,maxy[i]-len+1);
            int i2=min(n-len+1,minx[i]),j2=min(n-len+1,miny[i]);
            if(i1<=i2&&j1<=j2)
                c[i1][j1]++,c[i1][j2+1]--,c[i2+1][j1]--,c[i2+1][j2+1]++;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)c[i][j]+=c[i-1][j]+c[i][j-1]-c[i-1][j-1];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)if(m-c[i][j]==k||m-c[i][j]==k-1)
                return printf("1\n"),(void)0;
    }
    printf("2\n");
}
main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)scanf("%lld",&a[i][j]),m+=!t[a[i][j]]++;
    if(m<=k)return printf("%lld\n",k-m),0;
    return solve(),0;
}