算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
题目描述:
    在一个N*M(N<=200,M<=50000)像素的画板上画Q(Q<=50000)个图形,有矩形,圆形,倒等腰三角形,菱形四种,每个图形有九种颜色可选择。对于一个像素,后画的颜色会覆盖前面的颜色,请求出最后每种颜色的像素有多少个?
吐槽:
    1. 线段树会MLE...大概...
    2. ...并查集ms只能在这种问题上优化
算法分析:
    
    额,严格的说不是并查集啊... 只是在一个数组上乱搞出一个类似并查集的东西...
    现在我来简要讲述一下这个方法,这个方法非常好写,也就10行左右... 而且比线段树快很多~~
    我目前知道的这个优化必须要把所有的线段"一视同仁",插入线段[1,3]和[2,4]后,一同视为[1,4]....
    所以在任何时候,这个数组存的都是一段一段的不相交区间~~
    对于一个区间[l,r],l到r上的所有点的“代表”都是r+1.....
    如果要插入某线段[l',r'],那么从l'到r'扫一遍就可以了:
        如果某个点p代表是自己的话,那么就把p的代表改为Parent[r],然后检查p+1。
        如果p的代表不是自己的话,那么就检查parent[p]就可以了,因为parent[p]一定是未被覆盖的点。
    在查找p的代表中,用并查集中的“路径压缩”优化就可以了
 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 #define re(i,n) for(int i=0;i<n;i++)
 5 #define re1(i,n) for(int i=1;i<=n;i++)
 6 #define re2(i,n) for(int i=0;i<=n;i++)
 7 #define re3(i,n) for(int i=1;i<n;i++)
 8 const int N = 205;
 9 const int M = 50005;
10 int ans[10];
11 int seg[N][M];
12 int n,m,q;
13 void init(){
14     re(i,n) re2(j,m) {
15         seg[i][j] = j;
16     }
17     re(i,10) ans[i] = 0;
18 }
19 int find(int pos, int x){ return seg[pos][x] == x ? x: seg[pos][x] = find(pos,seg[pos][x]);}
20 void ins(int pos,int l, int r,int c){
21 //    cout<<pos<<" "<<l<<" "<<r-1<<" "<<c<<endl;
22     r = find(pos, r);
23     while(l < r) {
24         if(find(pos,l) == l){
25             ans[c] ++;
26             seg[pos][l] = r;
27             l++;
28         }
29         else {
30             l = seg[pos][l];
31         }
32     }
33 }
34 struct query{
35     int x,y,r,c,w,l;
36     char Q;
37 }num[M];
38 int main(){
39     while(~scanf("%d%d%d",&n,&m,&q)){
40         char ch[10];
41         init();
42         re(i,q) {
43             scanf("%s%d%d",ch,&num[i].x,&num[i].y);
44             num[i].Q = ch[0];
45             if(ch[0] == 'R'){
46                 scanf("%d%d%d",&num[i].l,&num[i].w,&num[i].c);
47             }
48             else if(ch[0] == 'T'){
49                 scanf("%d%d",&num[i].w,&num[i].c);
50             }
51             else {
52                 scanf("%d%d",&num[i].r,&num[i].c);    
53             }
54         }
55         for(int i=q-1;i>=0;i--){
56             int x = num[i].x,y=num[i].y, r= num[i].r, w=num[i].w,l = num[i].l,c = num[i].c;
57             if(num[i].Q=='C'){
58                 int left = max(y - r ,0), right = min(y + r, m-1);
59                 ins(x,left,right+1,c);
60                 for(int j = 1; j <= r; j++){
61                     if(x + j >= n && x - j < 0) break;
62                     while((y-left)*(y-left) + j*j > r*r) left ++;;
63                     while((right-y)*(right-y) + j*j > r*r) right--;
64                     if(x + j < n) ins(x + j, left, right +1 ,c);
65                     if(x - j >=0) ins(x - j, left, right +1 ,c);
66                 }
67             }
68             else if(num[i].Q=='D'){
69                 int left = max(y - r ,0), right = min(y + r, m-1);
70                 ins(x,left,right+1,c);
71                 for(int j = 1; j <= r; j++){
72                     if(x + j >= n && x - j < 0) break;
73                     while((y-left)+j > r) left ++;;
74                     while((right-y)+j > r) right--;
75                     if(x + j < n) ins(x + j, left, right +1 ,c);
76                     if(x - j >=0) ins(x - j, left, right +1 ,c);
77                 }
78             }
79             else if(num[i].Q=='R'){
80                 for(int X = x;X < n && X < x + l ; X++){
81                     ins(X,y,min(y+w,m),c);
82                 }
83             }
84             else {
85                 for(int X = x,W = w/2; X<n && W>=0; X++,W--){
86                     int left = max(0,y-W);
87                     int right = min(m-1,y+W);
88                     ins(X,left,right+1,c);
89                 }
90             }
91         }
92         re1(i,9) {cout<<ans[i]; if(i != 9) cout<<" ";} cout<<endl;
93     }
94 }
95 
posted on 2012-04-30 17:38 西月弦 阅读(426) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理