首页 > 其他分享 >CF1720E. Misha and Paintings

CF1720E. Misha and Paintings

时间:2022-09-01 23:01:08浏览次数:55  
标签:CF1720E 颜色 Paintings 斜线 sum Misha 正方形 左上 矩形

题意

给出n*n的矩阵,ai,j∈[1,n*n],现在要矩形覆盖若干次,每次把一个正方形的ai,j改为x,求最少的次数使得最后有k种不同的数

n<=500

题解

设sum为初始不同的数,若sum<k则显然只能一个个加,ans=k-sum

若sum>k,则有结论:ans<=2

证明:可以从(1,1)开始往右下扩展新颜色的矩形1,直到最后一次sum>k为止,右下角为(x,x)

然后从(x+1,x+1)向左上扩展矩形2,颜色和矩形1相同

设此时的种数为s,若把颜色均改为和之前出现的则为s-1,若把矩形2改成不同颜色的则为s+1

故可以取到[s-1,s+1]

因为每次扩展时s最多减2,故从>s跳到<s的过程中一定会经过[s-1,s+1],则必定有解


现在问题是怎么判断ans=1,3.5s+256MB

假设当前确定了一个矩形,则将其向左上或右下扩展影响不大

所以按斜线y-x=k来处理,把每种颜色所在的极大矩形提出,找到端点在斜线y-x=k上的极小正方形,则所有包含这个正方形的都可以除掉一种颜色

用f[i,j]记当前斜线,覆盖左上i号点右下j号点后除掉的颜色,二维前缀和解决

时间是斜线数n*(颜色数n^2+前缀和n^2),即O(n^3)

标签:CF1720E,颜色,Paintings,斜线,sum,Misha,正方形,左上,矩形
From: https://www.cnblogs.com/gmh77/p/16648132.html

相关文章

  • Codeforces Round #815 (Div. 2) E. Misha and Paintings
    人生中第一个AC的codeforces题,大概太难了,光是看答案就看了整整一下午,最后还是在b站上搜到讲解视频才明白的。俺们阿B真的是太厉害啦这道题首先容易看出当矩阵中数字个数......
  • [题解] Codeforces 1720 E Misha and Paintings 结论
    算是诈骗题?令一开始就存在的颜色数为cnt。k>=cnt的情况,显然每次找一个出现不止一次的颜色,然后把这个颜色的恰好一个方块替换成一种没有出现过的颜色就可以了,\(k-cnt\)次解......