首页 > ACM题库 > HDU-杭电 > hdu 2704 Bulletin Board-线段树-[解题报告]C++
2014
02-14

hdu 2704 Bulletin Board-线段树-[解题报告]C++

Bulletin Board

问题描述 :


The ACM Student Chapter has just been given custody of a number of school bulletin boards. Several members agreed to clear off the old posters. They found posters plastered many levels deep. They made a bet about how much area was left clear, what was the greatest depth of posters on top of each other, and how much of the area was covered to this greatest depth. To determine each bet’s winner, they made very accurate measurements of all the poster positions as they removed them. Because of the large number of posters, they now need a program to do the calculations. That is your job.
A simple illustration is shown above: a bulletin board 45 units wide by 40 high, with three posters, one with corners at coordinates (10, 10) and (35, 20), another with corners at (20, 25) and (40, 35), and the last with
corners at (25, 5) and (30, 30). The total area not covered by any poster is 1300. The maximum number of posters on top of each other is 2. The total area covered by exactly 2 posters is 75.

输入:

The input will consist of one to twenty data sets, followed by a line containing only 0. On each line the data will consist of blank separated nonnegative integers.
The first line of a dataset contains integers n w h, where n is the number of posters on the bulletin board, w and h are the width and height of the bulletin board. Constraints are 0 < n <= 100; 0 < w <= 50000; 0 < h <= 40000.
The dataset ends with n lines, each describing the location of one poster. Each poster is rectangular and has horizontal and vertical sides. The x and y coordinates are measured from one corner of the bulletin board. Each line contains four numbers xl yl xh and yh, where xl and yl, are the lowest values of the x and y coordinates in one corner of the poster and xh and yh are the highest values in the diagonally opposite corner.Each poster fits on the bulletin board, so 0 2 xl < xh 2 w, and 0 2 yl < yh 2 h.

输出:

The input will consist of one to twenty data sets, followed by a line containing only 0. On each line the data will consist of blank separated nonnegative integers.
The first line of a dataset contains integers n w h, where n is the number of posters on the bulletin board, w and h are the width and height of the bulletin board. Constraints are 0 < n <= 100; 0 < w <= 50000; 0 < h <= 40000.
The dataset ends with n lines, each describing the location of one poster. Each poster is rectangular and has horizontal and vertical sides. The x and y coordinates are measured from one corner of the bulletin board. Each line contains four numbers xl yl xh and yh, where xl and yl, are the lowest values of the x and y coordinates in one corner of the poster and xh and yh are the highest values in the diagonally opposite corner.Each poster fits on the bulletin board, so 0 2 xl < xh 2 w, and 0 2 yl < yh 2 h.

样例输入:

3 45 40
10 10 35 20
20 25 40 35
25 5 30 30
1 20 30
5 5 15 25
2 2000 1000
0 0 1000 1000
1000 0 2000 1000
3 10 10
0 0 10 10
0 0 10 10
0 0 10 10
0

样例输出:

1300 2 75
400 1 200
0 1 2000000
0 3 100

HDU_2704

    由于N很小,离散化之后暴力对每块格子染色应该都能过。效率比较好的办法之一是用线段树+扫描线来做(当然也可以离散化,不过这个题目W、H比较小,所以可以不必离散化),在线段树上记录当前扫描线上当前区间被覆盖的次数cnt,扫描线上被覆盖的长度len,被覆盖的最大深度dep,以及被覆盖的深度最大的部分的长度ml就可以了。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 210
#define MAXD 40010
int N, W, H, dep[4 * MAXD], ml[4 * MAXD], cnt[4 * MAXD], len[4 * MAXD];
struct Seg
{
    int x, y1, y2, c;
    bool operator < (const Seg &t) const
    {
        if(x == t.x) return c < t.c;
        return x < t.x;    
    }
    Seg(){}
    Seg(int _x, int _y1, int _y2, int _c) : x(_x), y1(_y1), y2(_y2), c(_c){}
}seg[MAXN];
void build(int cur, int x, int y)
{
    int mid = x + y >> 1, ls = cur << 1, rs = cur << 1 | 1;
    cnt[cur] = dep[cur] = len[cur] = 0, ml[cur] = y - x + 1;
    if(x == y) return ;
    build(ls, x, mid), build(rs, mid + 1, y);
}
void init()
{
    int i, x1, x2, y1, y2;
    scanf("%d%d", &W, &H);
    for(i = 0; i < N; i ++)
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        seg[i << 1] = Seg(x1, y1, y2, 1), seg[i << 1 | 1] = Seg(x2, y1, y2, -1);
    }
    std::sort(seg, seg + 2 * N);
    build(1, 1, H);
}
void update(int cur, int x, int y)
{
    int ls = cur << 1, rs = cur << 1 | 1;
    if(dep[ls] > dep[rs]) dep[cur] = dep[ls], ml[cur] = ml[ls];
    else if(dep[rs] > dep[ls]) dep[cur] = dep[rs], ml[cur] = ml[rs];
    else dep[cur] = dep[ls], ml[cur] = ml[ls] + ml[rs];
    dep[cur] += cnt[cur];
    if(cnt[cur]) len[cur] = y - x + 1;
    else len[cur] = len[ls] + len[rs];
}
void refresh(int cur, int x, int y, int s, int t, int c)
{
    int mid = x + y >> 1, ls = cur << 1, rs = cur << 1 | 1;
    if(x >= s && y <= t)
    {
        cnt[cur] += c;
        if(c > 0) ++ dep[cur], len[cur] = y - x + 1;
        else
        {
            -- dep[cur];
            if(cnt[cur]) len[cur] = y - x + 1;
            else
            {
                if(x == y) len[cur] = 0;
                else len[cur] = len[ls] + len[rs];    
            }
        }
        return ;
    }
    if(mid >= s) refresh(ls, x, mid, s, t, c);
    if(mid + 1 <= t) refresh(rs, mid + 1, y, s, t, c);
    update(cur, x, y);
}
void solve()
{
    int i, md, ans, area;
    area = md = ans = 0;
    seg[2 * N].x = seg[2 * N - 1].x;
    for(i = 0; i < 2 * N; i ++)
    {
        refresh(1, 1, H, seg[i].y1 + 1, seg[i].y2, seg[i].c);
        area += len[1] * (seg[i + 1].x - seg[i].x);
        if(dep[1] > md) md = dep[1], ans = ml[1] * (seg[i + 1].x - seg[i].x);
        else if(dep[1] == md) ans += ml[1] * (seg[i + 1].x - seg[i].x);
    }
    printf("%d %d %d\n", W * H - area, md, ans);
}
int main()
{
    while(scanf("%d", &N), N)
    {
        init();
        solve();
    }
    return 0;    
}

解题转自:http://www.cnblogs.com/staginner/archive/2012/08/27/2658259.html


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢