首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >给球上色(线段树+离散化) - HDU 1199

给球上色(线段树+离散化) - HDU 1199

作者头像
ACM算法日常
发布2019-01-02 13:16:43
1.2K0
发布2019-01-02 13:16:43
举报
文章被收录于专栏:ACM算法日常ACM算法日常

离散化是一中元素映射方法,它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中,只考虑需要用的值。离散化可以改进一个低效的算法,甚至实现根本不可能实现的算法。要掌握这个思想,必须从大量的题目中理解此方法的特点。例如,在建造线段树空间不够的情况下,可以考虑离散化。

使用STL算法离散化:

思路是:先排序,再删除重复元素,最后就是索引元素离散化后对应的值。

假定待离散化的序列为a[n],b[n]是序列a[n]的一个副本,则对应以上三步为:

sort(sub_a,sub_a+n);

//size为离散化后元素个数

int size=unique(sub_a,sub_a+n)-sub_a;

for(i=0;i<n;i++)

a[i]=lower_bound(sub_a,sub_a+size,a[i])-sub_a + 1;//k为b[i]经离散化后对应的值

对于第3步,若离散化后序列为0,1,2,...,size - 1则用lower_bound,从1,2,3,...,size则用upper_bound。其中lower_bound返回第1个不小于b[i]的值的指针,而upper_bound返回第1个大于b[i]的值的指针,当然在这个题中也可以用lower_bound然后再加1得到与upper_bound相同结果,两者都是针对以排好序列。使用STL离散化大大减少了代码量且结构相当清晰。

本题涉及离散化和线段树的应用,线段树采用数组实现,新手看起来较为吃力,可以多多琢磨实现思路。

Problem Description

There are infinite balls in a line (numbered 1 2 3 ....), and initially all of them are paint black. Now Jim use a brush paint the balls, every time give two integers a b and follow by a char 'w' or 'b', 'w' denotes the ball from a to b are painted white, 'b' denotes that be painted black. You are ask to find the longest white ball sequence.

有无限的球,排成一行,初始颜色为黑色。现在吉姆用一个刷子给球上色,整数a、b,w为白色,b为黑色。找出最长的白色序列。

Input

First line is an integer N (<=2000), the times Jim paint, next N line contain a b c, c can be 'w' and 'b'.

第一行是整数N,表示吉姆的绘制次数,后面N行包含2个数字和一个字母c,c表示w或者b。

There are multiple cases, process to the end of file.

多组测试用例

Output

Two integers the left end of the longest white ball sequence and the right end of longest white ball sequence (If more than one output the small number one). All the input are less than 2^31-1. If no such sequence exists, output "Oh, my god".

找出最长的白色序列。

数字小于2^31-1。

Sample Input

3 
1 4 w 
8 11 w 
3 5 b

Sample Output

8 11

解题思路:

1、输入区间,离散化区间

2、建立线段树,然后通过线段树对每个节点着色

3、依次计算连续区间的颜色

源代码:g++

#include <algorithm>
#include <stdio.h>
#include <string.h>

#define MAKE_ZERO(array) memset(array, 0, sizeof(array))
#define MAX_N 4020

int a[MAX_N], b[MAX_N], colors[MAX_N];
int tmp[2 * MAX_N], vis[MAX_N];

int cnt;

struct node {
    int l, r, col;
} segtree[MAX_N << 2];

//创建线段树
//数组存储(性能点)
void build(int rt, int l, int r) {
    if (l >= r)
        return ;

    //设置好区间值
    segtree[rt].l = l;
    segtree[rt].r = r;
    //创建阶段为0,黑色
    segtree[rt].col = 0;

    if (l == r - 1)
        return ;

    int mid = (l + r) / 2;
    //建立左子树,比如rt=1,左子树下标为2,右子树下标为3,依次类推
    build(rt << 1, l, mid);
    //创建右子树
    build(rt << 1 | 1, mid, r);
}

//为线段树的每个节点设置颜色
void update(int rt, int l, int r, int color) {
    if (l >= r) return ;

    int L = segtree[rt].l, R = segtree[rt].r;

    //说明这个位置是处于l和r之间的
    if (L <= l &&R <= r)
    {
        segtree[rt].col = color;
        return ;
    }

    //如果之前着色了,现在回产生分裂,不能通过这个父节点获取颜色了
    if (segtree[rt].col >= 0 && segtree[rt].col != color) {
        segtree[rt << 1].col = segtree[rt << 1 | 1].col = segtree[rt].col;
        segtree[rt].col = -1;
    }

    //继续遍历子节点
    int mid = (L + R) / 2;

    if ( l >= mid )
        update(rt << 1 | 1, l, r, color);
    else if ( r <= mid )
        update(rt << 1, l, r, color);
    else
    {
        update(rt << 1, l, mid, color);
        update(rt << 1 | 1, mid, r, color);
    }
}

//将线段树转为数组存储关键位置和颜色
void query(int rt) {
    int L = segtree[rt].l, R = segtree[rt].r;

    //只有大于0才能够决定这个区域的颜色,否则一直遍历到叶子节点
    if (segtree[rt].col >= 0) {
        for (int i = L; i < R; i++)
            vis[i] = segtree[rt].col;
        return ;
    }

    if (L == R) return ;
    //二维数组的树形结构
    query(rt << 1);
    query(rt << 1 | 1);
}

int main() {
    int n = 0;
    char color;
    //freopen("test.txt", "r", stdin);

    //n为区间数
    while (~scanf("%d", &n)) {
        cnt = 0;

        MAKE_ZERO(a);
        MAKE_ZERO(b);
        MAKE_ZERO(colors);
        MAKE_ZERO(tmp);

        for (int i = 0; i < n; i++) {
            //输入区间和颜色
            scanf("%d %d %c", &a[i], &b[i], &color);
            // 2
            // 1 3 w
            // 4 5 w 更新的是点,使右边加一,就变成连续的区间了。否则就更新不上去1~5这整块区间了
            b[i]++;
            //离散化位置
            tmp[cnt++] = a[i];
            tmp[cnt++] = b[i];

            //white对应1,black对应0
            if (color == 'w') {
                colors[i] = 1;
            }
        }

        //排序
        std::sort(tmp, tmp + cnt);

        //去掉重复
        cnt = std::unique(tmp, tmp + cnt) - tmp;

        //线段树
        build(1, 0, cnt);

        //更新每一个区间的颜色
        for (int i = 0; i < n; i++) {
            int p1, p2;
            p1 = std::lower_bound(tmp, tmp + cnt, a[i]) - tmp;
            p2 = std::lower_bound(tmp, tmp + cnt, b[i]) - tmp;
            update(1, p1, p2, colors[i]);
        }

        MAKE_ZERO(vis);
        //设置区域颜色
        query(1);

        tmp[cnt] = tmp[cnt - 1];
        int start = 0, end = 0, ts, te;

        for (int i = 0; i < cnt; i++) {
            //如果是黑色,不处理
            if ( vis[i] != 1 )
                continue;

            ts = tmp[i];

            while ( vis[i] == 1 )
                i++;

            if ( i > cnt )
                break;

            te = tmp[i];

            //比较区域大小
            if (te - ts > end - start)
            {
                end = te;
                start = ts;
            }
        }
        if (start == end)
            printf("Oh, my god\n");
        else
            printf("%d %d\n", start, end - 1);
        exit(0);
    }

    return 0;
}

对了,今天见到两个同事在玩一个竞技游戏,不过是编程竞技哈,和王者荣耀一个模式,撮合队伍后进如做题比赛,感觉很不错,推荐给大家玩玩。

网站:www.codingame.com

点击左下角的原文链接跳转~

来看个图,就是CLASH OF CODE模式,团队竞技~

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-12-27,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档