现在的位置: 首页 > 综合 > 正文

poj 2528 Mayor’s posters(线段树+离散化)

2018年03月17日 ⁄ 综合 ⁄ 共 2023字 ⁄ 字号 评论关闭

题意:有一块足够长的墙了给竞选人贴海报,后贴的可能会把衣面贴的给覆盖掉,问最有多少不同的海报是能看到的。

思路:线段树,因为坐标范围太大,无法表示,得离散化。

1.如何离散化。个人觉得 离散化是件危险的事,因为每次都会漏掉特殊情况,如此题
若样列为
1 6
1 2
5 6
用unique离散后就得如下对应关系
1 1 2 5 6 6

   1 2  3
如此求得的答案是能看见2块poster 因为它略去了中间的【3 4】段。但poj没有这样的测试数据,所以依然能过

所以离散化一定要特别特别注意区间被忽略的情况!!!!!。我用的方法是浪费一倍的空间,增加比它大一的点
如上例 pos 数组里将变以
pos : 1 1 2 2 2 3 5 6 6 6 7 7  离散化后为
                       2 3       5
这样原来漏掉的区点就由2这个点代替。

2.如何解些题。若按照它给的poster的顺序从前往后贴,你会发现无从下手,但是逆来,先贴后面的,贴它前一poster的时候,只要判断它的区间是否已被覆盖,覆盖了就不能再贴(因为是先把后来的poster给贴了)。

//1944K    47MS
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define L(u) (u<<1)
#define R(u) (u<<1|1)
const int M = 10005;

using namespace std;

struct Node
{
    int l,r;
    int cover;
}node[M<<4];
struct Seg
{
    int x,y;
}seg[M];
int pos[M<<2];

void Build (int u,int left,int right)
{
    node[u].l = left,node[u].r = right;
    node[u].cover = 0;
    if (node[u].l == node[u].r)
        return ;
    int mid = (node[u].l + node[u].r)>>1;
    Build (L(u),left,mid);
    Build (R(u),mid+1,right);
}
void Pushup(int u) //如果叶子都被覆盖了,则父结点的cover = 1
{
    if (node[L(u)].cover & node[R(u)].cover)
        node[u].cover = 1;
}
bool Query(int u,int left,int right)
{
    if (node[u].cover)
        return false;
    if (pos[node[u].l] == left&&pos[node[u].r] == right)//离散化后的映射关系
    {
        node[u].cover = 1;
        return true;
    }
    int mid  = (node[u].l + node[u].r)>>1;
    bool flag;
    if (right <= pos[mid]) flag = Query(L(u),left,right);
    else if (left >= pos[mid+1]) flag = Query(R(u),left,right);
    else flag =  Query(L(u),left,pos[mid])|Query(R(u),pos[mid+1],right);
    Pushup(u);
    return flag;
}
int main ()
{
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
    #endif
    int i,T,n,x,y,m;
    scanf ("%d",&T);
    while (T --)
    {
        scanf ("%d",&n);
        int k = 0;
        for (i = 0;i < n;i ++)
        {
            scanf ("%d%d",&seg[i].x,&seg[i].y);  //点增加1,避免离散化后,区间为遗漏
            pos[k++] = seg[i].x,pos[k++] = seg[i].y;
            pos[k++] = seg[i].x+1,pos[k++] = seg[i].y+1;
        }
        sort (pos,pos + k);
        m = (unique(pos,pos+k) - pos - 1);
        Build (1,0,m);
        int ans = 0;
        for (i = n-1;i >= 0;i --)
        {
            if (Query(1,seg[i].x,seg[i].y))
                ans ++;
        }
        printf ("%d\n",ans);
    }
    return 0;
}


抱歉!评论已关闭.