POJ PKU 2528 Mayor's posters 解题报告

题目链接: http://acm.pku.edu.cn/JudgeOnline/bbs?problem_id=2528

这题又是线段树+离散化

慢慢的对离散化有点感觉了,但是这题我还是错了3次

题目大意是一层一层地叠板子,问最后能看到几块

输入是板子的开始和结束位置

由于输入的是闭区间线段开始我就构造闭区间线段的线段树,但是后来发现很多问题,

比如构造线段树的时候有区间1-4–>1-2+3-4.如果1映射到位置1,2映射到4,3映射到8,4映射到12,那么5,6,7三个点就丢失了

所以后来改成了半开半闭区间,结果还是出了点问题,最后开成完全开区间才AC

也就是线段树表示两个端点,,比如位置1两端的端点是0和1,那么测试数据就有

(0 4)

(1 6)

(7 10)

(2 4)

(6 10)

五个开区间

然后在旧时一般的离散化+线段树了

贴代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 10005
struct node
{
    long l,r,h;
};
long buildTree(long l,long r,long pos);
void addHeight(long l,long r,long pos,long h);
void dealData(long &n,long pos);
node old[MAXN],newT[MAXN * 10];
bool isShowed[MAXN];
long tn,num,index[MAXN * 2];
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t --)
    {
        memset(old,0,sizeof(old));
        memset(newT,0,sizeof(newT));
        memset(index,0,sizeof(index));
        memset(isShowed,false,sizeof(isShowed));
        int i,j;
        num = tn = 0;
        scanf("%d",&n);
        for(i = 0 ; i < n ; i ++)
            scanf("%ld %ld",&old[i].l , &old[i].r) ,old[i].h = i + 1
            , index[num ++] = old[i].l - 1 , index[num ++] = old[i].r;
        sort(index , index + num);
        j = 1;
        for(i = 1 ; i < num ; i ++)
            if(index[i] != index[j - 1])
                index[j ++] = index[i];
        index[j] = index[j - 1] + 1;
        num = j;
        buildTree(0,num - 1, 1);
        for(i = 0 ; i < n ; i ++)
            addHeight(old[i].l - 1 , old[i].r ,1, old[i].h);
        dealData(tn , 1);
        j = 0;
        for(i = 0 ; i < MAXN ; i ++)
            j += isShowed[i]?1:0;
        printf("%d\n",j);
    }
    return 0;
}

long buildTree(long l,long r,long pos)
{
    newT[pos].l = l;
    newT[pos].r = r;
    newT[pos].h = 0;
    long mid = (l + r) >> 1;
    tn = (pos > tn)? pos : tn;
    if(r > l + 1)
        return 1 + buildTree(l , mid, 2 * pos) + buildTree(mid , r, 2 * pos + 1);
    else
        return 1;
}
void addHeight(long l,long r,long pos,long h)
{
    if(l == index[newT[pos].l] && r == index[newT[pos].r])
    {
        newT[pos].h = h;
        return;
    }
    if(newT[pos].l >= newT[pos].r)
        return;
    long mid = (newT[pos].l + newT[pos].r) >> 1;
    if(newT[pos].h)
    {
        newT[2 * pos].h = newT[pos].h;
        newT[2 * pos + 1].h = newT[pos].h;
        newT[pos].h = 0;
    }
    if(index[mid] >= r)
        addHeight(l,r,2 * pos, h);
    else if(index[mid] <= l)
        addHeight(l,r,2 * pos + 1, h);
    else
    {
        addHeight(l,index[mid],2 * pos, h);
        addHeight(index[mid],r,2 * pos + 1, h);
    }
}
void dealData(long &n,long pos)
{
    if(newT[pos].h)
    {
        isShowed[newT[pos].h] = true;
        return;
    }
    if(2 * pos <= tn)
        dealData(n,2 * pos);
    if(2 * pos + 1 <= tn)
        dealData(n,2 * pos + 1);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏everhad

设计模式:简单工厂和工厂方法

简单工厂概念 又叫做静态工厂方法(Static Factory Method)模式,由一个工厂对象决定创建出哪一种产品类的实例。 代码示例 Car是要得到的目标...

21560
来自专栏Java帮帮-微信公众号-技术文章全总结

第十四天 面向对象-eclipse导jar包&amp;修饰符&amp;自定义数据类型【悟空教程】

Ctrl+滑鼠左键 或者 F3 查看所选中类的源代码,当选中一个方法查看源代码时,会出现以下显示,上边为方法声明的位置,下边为方法实现的位置。

10320
来自专栏IMWeb前端团队

简洁的javascript编码(一)--变量、函数

本文作者:IMWeb jaychen 原文出处:IMWeb社区 未经同意,禁止转载 ? 一、变量 使用语义化的变量名称 Bad cons...

25790
来自专栏JackieZheng

初探JavaScript(四)——作用域链和声明提前

前言:最近恰逢毕业季,千千万万的学生党开始步入社会,告别象牙塔似的学校生活。往往在人生的各个拐点的时候,情感丰富,感触颇深,各种对过去的美好的总结,对未来的展望...

20650
来自专栏工科狗和生物喵

【计算机本科补全计划】C++牛客网试题习题解析

正文之前 一大早醒来,外面淅淅沥沥的雨绵绵的下着,床铺真的舒服,但是我也不能就在床上刷微博看小说吧,所以想起了昨晚下载的牛客网的APP,赶紧掏出我的大宝贝---...

39970
来自专栏Crossin的编程教室

真值表

逻辑判断是编程中极为常用的知识。之前的课我们已经说过,见第6课和第11课。但鉴于逻辑运算的重要性,今天我再把常用的运算结果总结一下,供大家参考。 这种被称为“真...

24340
来自专栏程序员的SOD蜜

JavaScript的“原型甘露”

今天跟朋友讨论JS的面向对象编程问题,想起了原来曾经看过一篇文章,但是看过很久想不起来了,用了很多关键词,终于用“悟透JavaScript  面向对象”这两个关...

27480
来自专栏数据结构与算法

洛谷P1043 数字游戏

题目描述 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前...

35450
来自专栏张善友的专栏

.NET不可变集合已经正式发布

微软基础类库(Base Class Library)团队已经完成了.NET不可变集合的正式版本,但不包括ImmutableArray。与其一起发布的还包括针对其...

238100
来自专栏zaking's

js算法初窥04(算法模式01-递归)

13620

扫码关注云+社区

领取腾讯云代金券