专栏文章

题解：CF1720E Misha and Paintings

MMutU
CF1720E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miol6kc7
此快照首次捕获于
2025/12/02 21:00
3 个月前
此快照最后确认于
2025/12/02 21:00
3 个月前
查看原文
数未修改矩阵中数的个数，记作 cntcnt。
若 cnt≥kcnt\ge k，显然答案为 cnt−kcnt-k。具体方式是一次填一个重复的颜色，颜色数加一，又可知一次操作最多使颜色数加一，所以这样一定最优。
若 cnt>kcnt>k，可以构造一种策略，通过两次操作完成要求。假设第一次操作选择一个左上角的正方形，令边长为 LL。满足当边长为 LL，操作后 cnt≥kcnt\ge k。当边长大于 LL，操作后 cnt<kcnt<k。第二个正方形右下角为 (L+1,L+1)(L+1,L+1)。随着第二个正方形边长 ++++，cntcnt 最多减少 22，于是最后 cnt=kcnt=k or cnt=k−1cnt=k-1。由于两个正方形颜色可以换，所以可以凑出 kk 种。
于是答案最多 22。考虑什么情况只用一个正方形覆盖。
枚举这个正方形长度。记 si,js_{i,j} 表示当前长度下左上角为 (i,j)(i,j) 的正方形覆盖后剩下几种颜色。注意到如果正方形覆盖了所有的某种颜色，它必定覆盖了这样一个正方形：(up,left)(up,left)，(down,right)(down,right)，其中四个变量分别表示该颜色最高最左最低最右的坐标。
考虑统计颜色贡献，根据该颜色的上下左右及正方形长度可以知道左上角位于哪一块的正方形能够覆盖这种颜色。二维差分即可。时间复杂度 O(n3)O(n^3)。

Code

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...