太难了,光是看答案就看了整整一下午,最后还是在b站上搜到讲解视频才明白的。俺们阿B真的是太厉害啦
这道题首先容易看出当矩阵中数字个数小于或等于所需要的个数时,直接输出他们的差即可。剩下的就是判断大于的情况。
这种情况的处理方法还多亏了大佬室友。像是个脑筋急转弯。但对我来说显然不是 可以证明在这种情况下,操作数至多为2,不是2就是1。证明方法是构造,总算知道tag里的构造算法是怎么回事了 首先从左上角开始往右下角画正方形,在正方形里填上同一种数字(颜色),直到整个方阵里的颜色种类恰好多余要求种类数,正方形再大一点就删过了。之后从这个正方形的右下的元素开始向左上方扩展正方形,由于和原来正方形重叠的部分已经被删过了,所以新的正方形每扩大一点,删除的颜色就会多2。也就是说用这样的删法,最终的颜色种类数与所要求的数字最多只会相差1,而这个1是可以通过恰当选择填充的颜色来避免的。这也就证明了操作数最多两步。
问题进而转化为能否一步完成。这个问题可以在n3解决。方法是先预处理数据,记录每种颜色在矩阵中最左上的坐标和最右下的坐标,框出一个矩形。然后枚举正方形的边长,从1到n。对于每一个边长,枚举每种颜色,根据颜色的边界坐标确定正方形要想框住所有的这种颜色,左上角定点所能在的范围,是一个矩形。只要所选的正方形的左上角顶点位于这个范围内,就能删除一种颜色。具体而言,一种颜色的左上角确定了正方形的右下界,颜色的右下角确定了正方形的左上界。下一步是根据正方形的界做标记。这里不能对这个矩形范围内的所有元素进行修改,因为这是n2的复杂度。这里应该用二维懒标记(2D lazy update)或者说二维差分。在范围的左上角加一,在右上角右边减一,在左下角下边减一,在右下角的右下加一。之后用计算前缀和的方法还原更新后的整个方阵。计算二维前缀和的方法是先扫描每一行,元素值为其行前缀和,再以此类推扫描每一列。还原后再用n^2时间扫描整个方阵,如果有一个元素满足n-k(颜色选择剩余部分已有的颜色)或者n-k+1(颜色选择不存在的颜色),则说明可以用一步完成,否则就只能两步完成了。
代码:
#include <iostream> using namespace std; bool m[250005]; struct color{ int r_min = 501, r_max = -1, c_min = 501, c_max = -1; } map[250005]; int main(){ int n, k; cin >> n >> k; int cat = 0; for(int i = 0; i<n; ++i){ for(int j = 0; j<n; ++j){ int x; cin >> x; if(!m[x]){ m[x] = 1; ++cat; } if(i<map[x].r_min) map[x].r_min = i; if(i>map[x].r_max) map[x].r_max = i; if(j<map[x].c_min) map[x].c_min = j; if(j>map[x].c_max) map[x].c_max = j; } } if(cat<=k){ cout << k-cat; return 0; } else{ for(int i = 1; i<=n; ++i){ int tmp[501][501] = {0}; for(int j = 1; j<250005; ++j){ if(m[j]&&map[j].r_max-map[j].r_min+1<=i&&map[j].c_max-map[j].c_min+1<=i){ int ul_r = (map[j].r_max-i+1<0?0:map[j].r_max-i+1); int ul_c = (map[j].c_max-i+1<0?0:map[j].c_max-i+1); int br_r = map[j].r_min+1; int br_c = map[j].c_min+1; tmp[ul_r][ul_c]++; tmp[ul_r][br_c]--; tmp[br_r][ul_c]--; tmp[br_r][br_c]++; } } for(int j = 0; j<=n-i; ++j){ int sum = 0; for(int t = 0; t<=n-i; ++t){ sum+=tmp[j][t]; tmp[j][t] = sum; } } for(int j = 0; j<=n-i; ++j){ int sum = 0; for(int t = 0; t<=n-i; ++t){ sum+=tmp[t][j]; tmp[t][j] = sum; if(sum==cat-k||sum==cat-k+1){ cout << 1; return 0; } } } } } cout << 2; return 0; }