首页 > 代码库 > SGU 177.Square
SGU 177.Square
时间限制：1.25s
空间限制：6M
题意：
给出n*n的矩阵（n<=1000）,和m次涂色（m<=5000），每次涂色将一个子矩阵涂成白色或黑色，后涂的颜色将覆盖掉前面的颜色。初始所有格子颜色为白色，求m次涂色后，矩阵中白色格子的数目。
Solution:
矩阵分割，在这道题里，只需要按照从后往前分割黑色的块，记录并累计每次分割后剩下的大小
最后用矩阵格子的总数目减去黑色块的大小就可以得到白色格子的数目
因此，在这道题我们只需要记录m次涂色的块，空间复杂度O（m）
对于随机数据的时间复杂度为O（m*n）
这题也可以用二维线段树做
code
/* 矩阵分割*/#include <iostream>#include <cstdio>using namespace std;int Gx[5009][2], Gy[5009][2];int color[5009];int n, m, sum;char c;void make (int p, int x1, int x2, int y1, int y2) { while (p<= m && (x1 > Gx[p][1] || x2 < Gx[p][0] || y1 > Gy[p][1] || y2 < Gy[p][0])) p++; if (p == m + 1) { sum += (x2 - x1+1) * (y2 - y1+1); return ; } int k1 = max (x1, Gx[p][0]); int k2 = min (x2, Gx[p][1]); if (x1 < k1) make (p + 1, x1, k1-1, y1, y2); if (x2 > k2) make (p + 1, k2+1, x2, y1, y2); x1 = k1, x2 = k2; k1 = max (y1, Gy[p][0]); k2 = min (y2, Gy[p][1]); if (y1 < k1) make (p + 1, x1, x2, y1, k1-1); if (y2 > k2) make (p + 1, x1, x2, k2+1, y2);}int main() { int x, y, x2, y2; scanf ("%d %d", &n, &m); for (int i = 1; i <= m; i++) { scanf ("%d %d %d %d %c", &x, &y, &x2, &y2, &c); Gx[i][0] = min (x, x2), Gy[i][0] = min (y, y2); Gx[i][1] = max (x, x2), Gy[i][1] = max (y, y2); color[i] = (c == ‘b‘ ? 1 : 0); } for (int i = m; i > 0; i--) { if (color[i] == 1) make (i + 1, Gx[i][0], Gx[i][1], Gy[i][0], Gy[i][1]); } printf ("%d", n*n-sum); return 0;}
SGU 177.Square
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。