pc网站优势,私人制定网站,抓取网站源码怎么做镜像,俄罗斯搜索引擎yandex推广UVA1493 - Draw a Mess(并查集) 题目链接 题目大意:一个N * M 的矩阵#xff0c;每次你在上面将某个范围上色#xff0c;不论上面有什么颜色都会被最新的颜色覆盖#xff0c;颜色是1-9#xff0c;初始的颜色是0.最后输出这个矩形中。每一个颜色有多少个。某个范围这个分为了… UVA1493 - Draw a Mess(并查集) 题目链接 题目大意:一个N * M 的矩阵每次你在上面将某个范围上色不论上面有什么颜色都会被最新的颜色覆盖颜色是1-9初始的颜色是0.最后输出这个矩形中。每一个颜色有多少个。某个范围这个分为了四种圆矩形菱形还有正三角形倒着的。注意这题的边界不能超出这个矩形非常easy越界。 解题思路由于题的矩阵范围是200 * 50000然后操作又是50000这样三个相乘即使给60s也是不够的。由于行的数目比較少。假设每次都能将这一行哪个没处理过直接拿出来。而不用一个一个推断就快非常多了这样一来就相当于每一个格子仅仅要遍历一次。所以这里就每行用一个并查集。标记这这个位置以及后面的位置能够上色的起始位置。然后颜色更新问题仅仅要将操作反着过来上色就能够处理了。 代码 #include cstdio
#include cstring
#include cmath
#include cstdlib
#include algorithmusing namespace std;
const int M 50005;
const int N 205;int f[N][M];
int G[N][M];
int color[10];
int n, m, q;
char str[N];struct OP {char type;int x, y, l, r, c;
}op[M];int getParent (int x, int y) { return y f[x][y] ? y : f[x][y] getParent (x, f[x][y]); } void init() { for (int i q - 1; i 0; i--) { scanf (%s, str); if (str[0] D) scanf (%d%d%d%d, op[i].x, op[i].y, op[i].l, op[i].c); else if (str[0] T) scanf (%d%d%d%d, op[i].x, op[i].y, op[i].l, op[i].c); else if (str[0] R) scanf (%d%d%d%d%d, op[i].x, op[i].y, op[i].l, op[i].r, op[i].c); else scanf (%d%d%d%d, op[i].x, op[i].y, op[i].l, op[i].c); op[i].type str[0]; } for (int i 0; i n; i) for (int j 0; j m; j) f[i][j] j; memset (color, 0, sizeof (color)); } void circle (int x, int y, int r, int c) { int L, R, s; for (int i -r; i r; i) { s sqrt(r * r - i * i); if (i x n || i x 0) continue; L max(y - s, 0); L max (getParent (i x, L), L); R min (s y, m - 1); for (int j L; j R; j) { if (j getParent (i x, j)) { color[c]; f[i x][j] R 1; } else j getParent(i x, j) - 1; } } } void diamond (int x, int y, int r, int c) { int L, R; for (int i -r; i r; i) { if (i x n || i x 0) continue; R min (r - abs(i) y, m - 1); L max (abs(i) - r y, 0); L max (L, getParent (i x, L)); for (int j L; j R; j) { if (j getParent (i x, j)) { color[c]; f[i x][j] R 1; } else j getParent (i x, j) - 1; } } } void rectangle (int x, int y, int l, int w, int c) { int L, R; for (int i x; i min(x l, n); i) { L max (y, getParent (i, y)); R min (y w - 1, m - 1); for (int j L; j R; j) { if (j getParent (i, j)) { color[c]; f[i][j] R 1; } else j getParent (i, j) - 1; } } } void triangle (int x, int y, int w, int c) { int L, R, h; h (w 1) / 2; for (int i 0; i h; i) { if (i x n) break; L max (y - h i 1, 0); L max (getParent(i x, L), L); R min (y h - i - 1, m - 1); for (int j L; j R; j) { if (j getParent (i x, j)) { color[c]; f[i x][j] R 1; } else j getParent (i x, j) - 1; } } } void solve () { for (int i 0; i q; i) { if (op[i].type D) diamond (op[i].x, op[i].y, op[i].l, op[i].c); else if (op[i].type C) circle (op[i].x , op[i].y, op[i].l, op[i].c); else if (op[i].type T) triangle (op[i].x, op[i].y, op[i].l, op[i].c); else rectangle (op[i].x, op[i].y, op[i].l, op[i].r, op[i].c); } } int main () { char str[N]; while (scanf (%d%d%d, n, m, q) ! EOF) { init (); solve(); for (int i 1; i 9; i) printf (%d , color[i]); printf (%d\n, color[9]); } return 0; } 转载于:https://www.cnblogs.com/mfrbuaa/p/5381511.html
