首页 > ACM题库 > HDU-杭电 > HDU 1543 Paint the Wall-线段树-[解题报告] C++
2013
12-12

HDU 1543 Paint the Wall-线段树-[解题报告] C++

Paint the Wall

问题描述 :

Here comes our future artist. See, he is painting again, this time on home’s white wall, using different color of paint. Let me see, red, yellow, black, green… but why does he just paint rectangles? Pretty guy, seems he is fond of it.

So, after he’s done his great job, the white wall has been filled with so many blocks of color. Of course, some color previously painted has been covered by some color painted later. Now, the little guy has some doubt that how many different colors have been left on the wall, and what are the areas of them. As a seven-year-old boy, he has just learned painting in kindergarten, math seems too difficult for him. So he turns to you, a college student good at math and programming, to help him figuring it out. Don’t make him disappointed.

输入:

Input consists of multiple test cases, each describing "a great job" done by out little guy.

Each case begins with a line containing two integers, Height and Width, the size of the wall. The next line contains an integer N, which is the number of rectangles that have been painted. N lines follow, describing the rectangles in the order they were painted. Each line contains five integers, Top, Left, Bottom, Right, and Color, giving out the position, size and color information of the rectangle.

The range of Height and Width is [1, 10000]. There will be at least 1, and at most 100 rectangles to be painted. For each rectangle, Top and Bottom is in the range [0, Height], Left and Right is in the range [0, Width]. Bottom is strictly greater than Top, and Right is strictly greater than Left. Color will be in the range [1, 100].

The top-left coordinate of the wall is (0, 0), and the bottom-right coordinate of the wall is (Height, Width), as shown below.



(0,0) (0,W)
---------------
| |
| |
| |
| |
| |
---------------
(H,0) (H,W)

The last case is followed by a line containing two zeroes.

There is a blank line between two test cases.

输出:

For each painting, first output "Case X:" in a single line where X is the case number starting form 1. Then output the colors left and their areas, one color per line, in the order of color numbers (increasing). For each color, you should output the color number, a blank space, and the area of this color on the wall. After that, you should output a single line "There is M color left on the wall." or "There are M colors left on the wall.", depending on M, which is the number of colors left on the wall.

Output a blank line between two test cases.

样例输入:

10 5
1
1 1 2 2 2

4 4
2
0 0 3 3 1
2 2 4 4 2

0 0

样例输出:

Case 1:
2 1
There is 1 color left on the wall.

Case 2:
1 8
2 4
There are 2 colors left on the wall.

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1543

题目大意:给墙壁上色(把某一片正方形涂色),上过色的地方还可以再上色,但是颜色会变为最新刷的颜色,求刷完之后每种颜色的面积和在墙上能看到几个颜色.

题目思路:
不知道谁把这题归到线段树= =,果断的二维区间更新去想,但是想不到外层树怎么更新,本来准备试试矩形树(没用过),结果结果…暴力了.
把x和y离散化,之后暴力更新和暴力求面积.
矩形树的代码也贴了.
不过小数据看不出矩形树的优势的,不过矩形树超过了1000,数组也很难开.

代码(暴力):

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <time.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define ull unsigned __int64
#define ll __int64
//#define ull unsigned long long
//#define ll long long
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define middle (l+r)>>1
#define MOD 1000000007
#define esp (1e-4)
const int INF=0x3F3F3F3F;
const double DINF=10001.00;
//const double pi=acos(-1.0);
const int N=110;
int n,m;
int mtx[N<<1][N<<1],X[N<<1],Y[N<<1],xc,yc,cnt[N];
struct node{
	int x1,y1,x2,y2,c;
	void write(){
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
		if(x1>x2) swap(x1,x2);
		if(y1>y2) swap(y1,y2);
	}
}a[N];

int bs(int key,int size,int A[]){
	int l=0,r=size-1,mid;
	while(l<=r){
		mid=middle;
		if(key>A[mid]) l=mid+1;
		else if(key<A[mid]) r=mid-1;
		else return mid;
	}return -1;
}

int main(){
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	int i,j,k,w,h,x1,y1,x2,y2;
	int T,cas=0;//scanf("%d",&T);for(cas=1;cas<=T;cas++)
	while(~scanf("%d%d",&w,&h)){
		if(w==h && !w) break;
		scanf("%d",&n);
		for(i=m=0;i<n;i++){
			a[i].write();
			X[m]=a[i].x1,Y[m]=a[i].y1,m++;
			X[m]=a[i].x2,Y[m]=a[i].y2,m++;
		}
		sort(X,X+m);sort(Y,Y+m);
		for(i=xc=1;i<m;i++) if(X[i]!=X[i-1]) X[xc++]=X[i];
		for(i=yc=1;i<m;i++) if(Y[i]!=Y[i-1]) Y[yc++]=Y[i];
		memset(mtx,0,sizeof(mtx));
		for(i=0;i<n;i++){
			x1=bs(a[i].x1,xc,X),x2=bs(a[i].x2,xc,X);
			y1=bs(a[i].y1,yc,Y),y2=bs(a[i].y2,yc,Y);
			for(j=x1;j<x2;j++)
				for(k=y1;k<y2;k++)
					mtx[j][k]=a[i].c;
		}
		memset(cnt,0,sizeof(cnt));
		for(i=0;i<xc;i++){
			for(j=0;j<yc;j++) if(mtx[i][j]){
				cnt[mtx[i][j]]+=(X[i+1]-X[i])*(Y[j+1]-Y[j]);
			}
		}
		if(cas) puts("");
		printf("Case %d:\n",++cas);
		for(i=1,n=0;i<=100;i++)if(cnt[i]){
			n++;
			printf("%d %d\n",i,cnt[i]);
		}
		if(n==1) printf("There is %d color left on the wall.\n",n);
		else printf("There are %d colors left on the wall.\n",n);
	}
	return 0;
}

(2)矩形树代码

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <time.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define ull unsigned __int64
#define ll __int64
//#define ull unsigned long long
//#define ll long long
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define middle (l+r)>>1
#define MOD 1000000007
#define esp (1e-4)
const int INF=0x3F3F3F3F;
const double DINF=10001.00;
//const double pi=acos(-1.0);
const int N=110;
int n,m;
int X[N<<1],Y[N<<1],xc,yc;
int cov[(N*N)<<6],vis[N],cnt;

struct node{
    int xl,xr,yl,yr;
    int xmid(){return (xl+xr)>>1;}
    int ymid(){return (yl+yr)>>1;}
};

node New(int xl,int xr,int yl,int yr){
    node r;
    r.xl=xl,r.xr=xr;
    r.yl=yl,r.yr=yr;
    return r;
}

struct rct{
    int x1,y1,x2,y2,c;
    void write(){
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        if(x1>x2) swap(x1,x2);
        if(y1>y2) swap(y1,y2);
    }
}a[N];

int bs(int key,int size,int A[]){
    int l=0,r=size-1,mid;
    while(l<=r){
        mid=middle;
        if(key>A[mid]) l=mid+1;
        else if(key<A[mid]) r=mid-1;
        else return mid;
    }return -1;
}

void PushDown(int rt){
    if(cov[rt]!=-1){
        cov[(rt<<2)-2]=cov[(rt<<2)-1]=cov[rt];
        cov[rt<<2]=cov[rt<<2|1]=cov[rt];
        cov[rt]=-1;
    }
}

void Update(node p,int rt,node P,int c){
    if((P.xl<=p.xl&&p.xr<=P.xr) && (P.yl<=p.yl&&p.yr<=P.yr)){
        cov[rt]=c;
        return;
    }
    PushDown(rt);
    int xmid=p.xmid(),ymid=p.ymid();
    if(P.xl<=xmid){
        if(P.yl<=ymid) Update(New(p.xl,xmid,p.yl,ymid),(rt<<2)-2,P,c);
        if(ymid<P.yr) Update(New(p.xl,xmid,ymid+1,p.yr),(rt<<2)-1,P,c);
    }
    if(xmid<P.xr){
        if(P.yl<=ymid) Update(New(xmid+1,p.xr,p.yl,ymid),rt<<2,P,c);
        if(ymid<P.yr) Update(New(xmid+1,p.xr,ymid+1,p.yr),rt<<2|1,P,c);
    }
}

void Query(node p,int rt){
    if(cov[rt]!=-1){
        vis[cov[rt]]+=(X[p.xr+1]-X[p.xl])*(Y[p.yr+1]-Y[p.yl]);
        return;
    }
    if(p.xl==p.xr && p.yl==p.yr) return;
    PushDown(rt);
    int xmid=p.xmid(),ymid=p.ymid();
    Query(New(p.xl,xmid,p.yl,ymid),(rt<<2)-2);
    if(ymid<p.yr) Query(New(p.xl,xmid,ymid+1,p.yr),(rt<<2)-1);
    if(xmid<p.xr){
        Query(New(xmid+1,p.xr,p.yl,ymid),rt<<2);
        if(ymid<p.yr) Query(New(xmid+1,p.xr,ymid+1,p.yr),rt<<2|1);
    }
}

int main(){
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    int i,j,k,r,c,x1,y1,x2,y2;
    int T,cas=0;//scanf("%d",&T);for(cas=1;cas<=T;cas++)
    while(~scanf("%d%d",&r,&c)){
        if(r==c && !r) break;
        scanf("%d",&n);
        for(i=m=0;i<n;i++){
            a[i].write();
            X[m]=a[i].x1,Y[m]=a[i].y1,m++;
            X[m]=a[i].x2,Y[m]=a[i].y2,m++;
        }
        sort(X,X+m);sort(Y,Y+m);
        for(i=xc=1;i<m;i++) if(X[i]!=X[i-1]) X[xc++]=X[i];
        for(i=yc=1;i<m;i++) if(Y[i]!=Y[i-1]) Y[yc++]=Y[i];
        memset(cov,-1,sizeof(cov));
        for(i=0;i<n;i++){
            x1=bs(a[i].x1,xc,X),x2=bs(a[i].x2,xc,X)-1;
            y1=bs(a[i].y1,yc,Y),y2=bs(a[i].y2,yc,Y)-1;
            Update(New(0,xc-2,0,yc-2),1,New(x1,x2,y1,y2),a[i].c);
        }
        memset(vis,0,sizeof(vis));
        Query(New(0,xc-2,0,yc-2),1);
        if(cas) puts("");
        printf("Case %d:\n",++cas);
        for(cnt=0,i=1;i<=100;i++) if(vis[i]){
            cnt++;
            printf("%d %d\n",i,vis[i]);
        }
        if(cnt==1) puts("There is 1 color left on the wall.");
        else printf("There are %d colors left on the wall.\n",cnt);
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/gotoac/article/details/7569956


  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测