ZOJ 2747 Paint the Wall（离散化+暴力）题解

题意：给你一个面，然后涂颜色，问你最后剩多少颜色，每种颜色面积。

思路：第一反应是二维线段树，代码又臭又长，可以做。但是这题暴力+离散化就可以过。可以看到他给的n只有100，也就是说最坏情况下会涂100次，每次最多涂200*200个点，那么完全可以用暴力。有一个地方纠结了半天，原题每一格代表了面积，我们离散化后每一格代表的是坐标点，所以我在涂面积时在起始位置+1后的位置开始涂，在算面积时，坐标左边就是涂的面积。

代码：

#include<set>

#include<map>

#include<cstdio>

#include<utility>

#include<cmath>

#include<stack>

#include<vector>

#include<queue>

#include<cstring>

#include<string>

#include<sstream>

#include<iostream>

#include<algorithm>

#define ll long long

#define ull unsigned long long

using namespace std;

const int maxn = +;

const int seed = ;

const int MOD = ;

const int INF = 0x3f3f3f3f;

struct node{

    int x1,y1,x2,y2,color;

}q[maxn];

int x[maxn << ],y[maxn << ];    //离散

int mp[maxn << ][maxn << ];

int color[maxn];

int main(){

    int h,w;

    int n,Case = ;

    while(~scanf("%d%d",&h,&w) && h + w){

        scanf("%d",&n);

        int num1 = ,num2 = ;

        for(int i = ;i <= n;i++){

            scanf("%d%d%d%d%d",&q[i].x1,&q[i].y1,&q[i].x2,&q[i].y2,&q[i].color);

            x[num1++] = q[i].x1,x[num1++] = q[i].x2;

            y[num2++] = q[i].y1,y[num2++] = q[i].y2;

        }

        sort(x,x + num1);

        sort(y,y + num2);

        num1 = unique(x,x + num1) - x;

        num2 = unique(y,y + num2) - y;

        memset(mp,,sizeof(mp));

        memset(color,,sizeof(color));

        for(int k = ;k <= n;k++){

            int x1 = lower_bound(x,x + num1,q[k].x1) - x;

            int x2 = lower_bound(x,x + num1,q[k].x2) - x;

            int y1 = lower_bound(y,y + num2,q[k].y1) - y;

            int y2 = lower_bound(y,y + num2,q[k].y2) - y;

            for(int i = x1 + ;i <= x2;i++){

                for(int j = y1 + ;j <= y2;j++){

                    mp[i][j] = q[k].color;

                }

            }

        }

        for(int i = ;i < num1;i++){

            for(int j = ;j <= num2;j++){

                if(mp[i][j]){

                    color[mp[i][j]] += (x[i] - x[i - ])*(y[j] - y[j - ]);

                }

            }

        }

        if(Case != ) printf("\n");

        printf("Case %d:\n",Case++);

        int num = ;

        for(int i = ;i <= ;i++){

            if(color[i]){

                printf("%d %d\n",i,color[i]);

                num++;

            }

        }

        if(num == ){

            printf("There is 1 color left on the wall.\n");

        }

        else{

            printf("There are %d colors left on the wall.\n",num);

        }

    }

    return ;

}

巴特西

ZOJ 2747 Paint the Wall（离散化+暴力）题解

最新文章

热门文章