题解：CF1720E Misha and Paintings

MutU · 2025-08-01 07:54:19 · 题解

数未修改矩阵中数的个数，记作 cnt。

若 cnt\ge k，显然答案为 cnt-k。具体方式是一次填一个重复的颜色，颜色数加一，又可知一次操作最多使颜色数加一，所以这样一定最优。

若 cnt>k，可以构造一种策略，通过两次操作完成要求。假设第一次操作选择一个左上角的正方形，令边长为 L。满足当边长为 L，操作后 cnt\ge k。当边长大于 L，操作后 cnt<k。第二个正方形右下角为 (L+1,L+1)。随着第二个正方形边长 ++，cnt 最多减少 2，于是最后 cnt=k or cnt=k-1。由于两个正方形颜色可以换，所以可以凑出 k 种。

于是答案最多 2。考虑什么情况只用一个正方形覆盖。

枚举这个正方形长度。记 s_{i,j} 表示当前长度下左上角为 (i,j) 的正方形覆盖后剩下几种颜色。注意到如果正方形覆盖了所有的某种颜色，它必定覆盖了这样一个正方形：(up,left)，(down,right)，其中四个变量分别表示该颜色最高最左最低最右的坐标。

考虑统计颜色贡献，根据该颜色的上下左右及正方形长度可以知道左上角位于哪一块的正方形能够覆盖这种颜色。二维差分即可。时间复杂度 O(n^3)。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 510;
int n,k,cnt;
int a[N][N],u[N*N],d[N*N],l[N*N],r[N*N];
int vis[N*N],sum[N][N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>k;
    memset(u,60,sizeof(u));
    memset(d,0,sizeof(d));
    memset(l,60,sizeof(l));
    memset(r,0,sizeof(r));
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
        cin>>a[i][j];
        if(!vis[a[i][j]]) vis[a[i][j]]=++cnt;
        a[i][j]=vis[a[i][j]];
        u[a[i][j]]=min(u[a[i][j]],i);
        d[a[i][j]]=max(d[a[i][j]],i);
        l[a[i][j]]=min(l[a[i][j]],j);
        r[a[i][j]]=max(r[a[i][j]],j);
    }
    if(k>=cnt) cout<<k-cnt;
    else{
        for(int len=1;len<=n;len++){
            memset(sum,0,sizeof(sum));
            for(int i=1;i<=cnt;i++){
                int x=d[i]-len+1,y=r[i]-len+1;
                int xx=u[i],yy=l[i];
                if(x<=0) x=1;
                if(y<=0) y=1;
                if(xx+len-1>n) xx=n-len+1;
                if(yy+len-1>n) yy=n-len+1;
                if(x<=xx && y<=yy){
                    //cout<<len<<' '<<i<<' '<<x<<' '<<y<<' '<<xx<<' '<<yy<<'\n';
                    sum[x][y]++;
                    sum[x][yy+1]--;
                    sum[xx+1][y]--;
                    sum[xx+1][yy+1]++;
                }
            }
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j];
                    if(cnt-sum[i][j]==k || cnt-sum[i][j]==k-1){
                        //cout<<len<<' '<<i<<' '<<j<<' '<<sum[i][j]<<'\n';
                        cout<<1;
                        return 0;
                    }
                }
            }
        }
        cout<<2;
    }
    return 0;
}