Articles tagged as

  1. [URAL1028] Stars (Using SBT, SBST, VBST)

    Time Limit: 0.25 second

    Memory Limit: 16 MB

    Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.

    image0

    For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it’s formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.

    You are to write a program that will count the amounts of the stars of each level on a given map.

    Input

    The first line of the input contains a number of stars N (1 ≤ N ≤ 15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space ...

  2. [ZOJ1610] Count the Colors

    Time limit: 1 Seconds

    Memory limit: 32768K

    Painting some colored segments on a line, some previously painted segments may be covered by some the subsequent ones.

    Your task is counting the segments of different colors you can see at last.

    Input

    The first line of each data set contains exactly one integer n, 1 <= n <= 8000, equal to the number of colored segments.

    Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:

    x1 x2 c

    x1 and x2 indicate the left endpoint and right endpoint of the segment, c indicates the color of the segment.

    All the numbers are in the range [0, 8000], and they are all integers.

    Input may contain several data set, process to the end of file.

    Output

    Each line of the output should contain a color index that can be seen from the top, following the count of the segments of this color, they should be printed according to the color index.

    If some color can’t be seen, you shouldn’t print it.

    Print a blank line after every dataset.

    Source

    ZOJ Monthly, May 2003

    Solution

    第一个用线段树过的题目啊~~呵呵。基础题目,虽然对我来说并不简单。在处理最后数线段条数的问题上颇费了些周折,先是问大牛,结果没搞懂,就自力更生地写出来了。。。

    话说特别巧,我刚好是第1000个过这道题的人,哈哈 ...

  3. Size Balanced Tree in C++

    修改是在上一个版本的基础上进行的,从ghost那学了两个小技巧(是什么呢?呵呵~),一下子使得维护部分的代码量减少了一半,并且减少了烦琐的判空,这样代码的实际长度就在90行左右了,“宽度”也减小了不少。代码中有的地方注明了是“维护p”,那是由于有的时候维护父指针p(arent)会方便些。如果不需要,直接删掉这些语句就行了。当然,还有其它一些小改动。

    觉得如果没有错误的话就没有必要再继续改动了。再改动也不可能改变它的时间复杂度,顶多是优化一下常数,我打算尽早开始背了准备比赛吧。

    当然如果你发现了程序中哪些不合理的地方导致了速度变慢也请指出,谢谢……

    (为什么我的sbt会比ghost的treap慢呢,旋转的次数也比他的少多了啊,郁闷~)

    1. 修改了Delete的函数原型说明:它与后面的Delete函数算法描述部分的不一致。
    2. 删除了Insert部分中关于具有相同关键字节点插入子树的左右说明:它显然是不对的(我竟然一直没意识到直至我的ural1028SBT版用rank后 WA掉),因为一Maintain原来插入的位置就有可能变化。

    ——2007年6月21日更新

    加入了退化版SBT的说明(在Maintain处)。经测试在一般数据下退化版的确实要快——这在OI比赛中也许很实用。

    ——2007年7月2日更新

    小更新。完善了部分注释,并且把delete里的两句做了优化,使之更短更快。修改了rank,把每次对于i和size关系的判断(它事实上只需要进行一次)写到了注释里,要求i<=T->size,否则每次都要判断实在太慢了。把.cc的扩展名改成了.h,因为我默写的时候都是把SBT默写到一个.h文件里,然后用另外一个写好的cpp文件调用它来检查对错。这样也许会方便些吧。

    ——2007年7月6日更新

    /****************************************
    *                 SBT.h
    *
    *       Fri Jul 18 20:40:08 2007
    *       Copyright  2007  巨菜逆铭
    *
    ******************************************/
    
    #include <iostream>
    #include <cassert>
    using namespace std;
    
    //————SBT的储存结构————
    struct SBTNode{
        SBTNode *ch[2],*p;    //ch[0]、ch[1]分别为左右孩子,p为双亲
        long key;    //这里省略了卫星数据域
        unsigned long size;
        SBTNode(long _key,unsigned long _size);
    }NIL=SBTNode(0,0);
    typedef SBTNode *SBTree;
    SBTNode::SBTNode(long _key,unsigned long _size=1){ //构造函数:未考虑卫星数据
        ch[0]=ch[1]=p=&NIL;
        size=_size;
        key=_key;
    }
    
    //————SBT基本操作函数原型说明————
    SBTNode *SBT_Search(SBTree T,long key);
        //在T中中寻找关键字为key的结点
        //若能找到则返回指向它的指针,否则返回NULL
    void SBT_Insert(SBTree &T, SBTNode* x);
        //将节点x插入树中
    SBTNode *SBT_Delete(SBTree &T, long key);
        //从以T为根的SBT中删除一个关键字为key的结点并返回“实际”被删除结点的指针
        //如果树中没有一个这样的结点,删除搜索到的最后一个结点并返回其指针
    SBTNode *SBT_Pred(SBTree T, long key);
        //返回指向关键字为key的节点在T的中序遍历中的直接前趋的指针
        //要求T中必须有关键字为key的节点
    SBTNode *SBT_Succ(SBTree T,long key);
        //返回指向关键字为key的节点在T的中序遍历中的直接后继的指针
        //要求T中必须有关键字为key的节点
    SBTNode *SBT_Select(SBTree T, unsigned long i);
        //从树T中找到关键字第i小的结点并返回其指针
    unsigned long SBT_Rank(SBTree T, long key);
        //返回关键字为key的节点在树T中的秩
        //若不存在此节点则返回0
    
    //————SBT的修复操作的算法描述 ...

Page 1 / 1