题目大意：给出n＊m的点，可以在上用不同颜色的笔画矩形，菱形，等腰三角形和圆形，因为是一个一个画的，所以有的点会被覆盖掉，原先的颜色就会被覆盖掉了。现在给出每个人画的图案和顺序，问最后每种颜色占了多少个点
解题思路：如果直接暴力的话就会TLE 为了防止被覆盖，就倒着画，如果该点被占有了，就不可以再画了 我们用并查集将每一个点所能到达的最右端的点纪录下来，将那些被使用过的点并起来，然后依次从上往下扫
参考了学长的代码。。。
#include #include #include #include #include #include #define maxn 210 #define maxm 50010 using namespace std; int w[maxn][maxm], N, M, q; int color[10]; map Map; struct Shape{ int x, y, r, w, c, m, Start, End; void init() { if(m < 2) { Start = max(0,x - r); End = min(N - 1, x + r); } else{ r = (r + 1) / 2 - 1; Start = x; End = min(N - 1, r + x); } } }S[maxm]; int find(int *f, int x) { return x == f[x] ? x : f[x] = find(f, f[x]); } void init() { for(int i = 0; i < N; i++) for(int j = 0; j <= M; j++) w[i][j] = j; for(int i = 0; i < 10; i++) color[i] = 0; char str[20]; for(int i = 0; i < q; i++) { scanf("%s", str); S[i].m = Map[str[0]]; if(str[0] != 'R') { scanf("%d%d%d%d",&S[i].x, &S[i].y, &S[i].r, &S[i].c); S[i].init(); } else{ scanf("%d%d%d%d%d", &S[i].x, &S[i].y, &S[i].r, &S[i].w, &S[i].c); } } } int count_Rec(int x, int y, int r, int W) { int cnt = 0; for(int i = x; i <= x + r - 1 && i < N; i++) { int t = y; while(t = find(w[i],t), abs(t - y) < W && t < M) { cnt++; w[i][t] = t + 1; } } return cnt; } int get_R(int x, int i, int r, int m) { if(m == 0) return (int)sqrt(1.0 * r * r - 1.0 * (x - i) * (x - i)); else if(m == 1) return r - abs(x - i); else if(m == 2 ) return r - (i - x); return 0; } int count_Oth(int x, int y, int r, int m, int Start, int End) { int cnt = 0; for(int i = Start; i <= End; i++) { int R = get_R(x, i, r, m); int t = max(0, y - R); while(t = find(w[i], t) , abs(t - y) <= R && t < M) { cnt++; w[i][t] = t + 1; } } return cnt; } void solve() { for(int i = q - 1; i >= 0; i--) { int &col = color[S[i].c]; if(S[i].m == 3) col += count_Rec(S[i].x, S[i].y, S[i].r, S[i].w); else col += count_Oth(S[i].x, S[i].y, S[i].r, S[i].m,S[i].Start, S[i].End); } printf("%d", color[1]); for(int i = 2; i < 10; i++) printf(" %d", color[i]); printf("\n"); } void begin() { Map['C'] = 0; Map['D'] = 1; Map['T'] = 2; Map['R'] = 3; } int main() { begin(); while(scanf("%d%d%d", &N, &M, &q) != EOF) { init(); solve(); } return 0; }