Articles tagged as

  1. [CEOI99][POJ1733][URAL1003][VIJOS1112] Parity Game

    Time Limit:1000MS

    Memory Limit:65536K

    Description

    Now and then you play the following game with your friend. Your friend writes down a sequence consisting of zeroes and ones. You choose a continuous subsequence (for example the subsequence from the third to the fifth digit inclusively) and ask him, whether this subsequence contains even or odd number of ones. Your friend answers your question and you can ask him about another subsequence and so on. Your task is to guess the entire sequence of numbers.

    You suspect some of your friend’s answers may not be correct and you want to convict him of falsehood. Thus you have decided to write a program to help you in this matter. The program will receive a series of your questions together with the answers you have received from your friend. The aim of this program is to find the first answer which is provably wrong, i.e. that there exists a sequence satisfying answers to all the previous questions, but no such sequence satisfies this answer.

    Input

    The first line of input contains one number, which is the length of the sequence of zeroes and ones. This length is less or equal ...

  2. [NOI 02] 银河英雄传说

    时限:2s

    问题描述

    公元五八○一年,地球居民迁移至金牛座α第二行星,在那里发表银河联邦创立宣言,同年改元为宇宙历元年,并开始向银河系深处拓展。

    宇宙历七九九年,银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征,气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。

    杨威利擅长排兵布阵,巧妙运用各种战术屡次以少胜多,难免恣生骄气。在这次决战中,他将巴米利恩星域战场划分成30000列,每列依次编号为1, 2, …, 30000。之后,他把自己的战舰也依次编号为1, 2, …, 30000,让第i号战舰处于第i列(i = 1, 2, …, 30000),形成“一字长蛇阵”,诱敌深入。这是初始阵形。当进犯之敌到达时,杨威利会多次发布合并指令,将大部分战舰集中在某几列上,实施密集攻击。合并指令为M i j,含义为让第i号战舰所在的整个战舰队列,作为一个整体(头在前尾在后)接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。

    然而,老谋深算的莱因哈特早已在战略上取得了主动。在交战中,他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。

    在杨威利发布指令调动舰队的同时,莱因哈特为了及时了解当前杨威利的战舰分布情况,也会发出一些询问指令:C i j。该指令意思是,询问电脑,杨威利的第i号战舰与第j号战舰当前是否在同一列中,如果在同一列中,那么它们之间布置有多少战舰。

    作为一个资深的高级程序设计员,你被要求编写程序分析杨威利的指令,以及回答莱因哈特的询问。

    最终的决战已经展开,银河的历史又翻过了一页……

    输入文件

    输入文件galaxy.in的第一行有一个整数T(1<=T<=500,000),表示总共有T条指令。

    以下有T行,每行有一条指令。指令有两种格式:

    M i j :i和j是两个整数(1<=i , j<=30000),表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令,并且保证第i号战舰与第j号战舰不在同一列。 C i j :i和j是两个整数(1<=i , j<=30000),表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。

    输出文件

    输出文件为galaxy.out。你的程序应当依次对输入的每一条指令进行分析和处理:

    如果是杨威利发布的舰队调动指令,则表示舰队排列发生了变化,你的程序要注意到这一点,但是不要输出任何信息;

    如果是莱因哈特发布的询问指令,你的程序要输出一行,仅包含一个整数,表示在同一列上,第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上,则输出-1。

    题解

    并查集。把每个战舰队列作为一个集合。两个战舰队列的合并就可以看作两个集合的合并。

    这里我们需要处理集合内元素间的关系:得到两个元素之间的元素个数。把所有元素按顺序储存需要的时候再数显然是不划算的。我们可以为每个节点维护一个dist域,记录此元素到到父节点的距离。显然如果要求两个元素i、j间的距离,我们需要先通过路径压缩使得他们的父节点统一为根,然后只要|dist[i]-dist[j]|-1就行了。

    但是在合并两个集合时怎么维护dist呢?我们这里再引入一个size域,仅当i为战舰队列的头头时才有效。它表示集合中元素的个数。这样,在做合并时,就很容易维护dist了。问题解决。

    代码:

    #include <cstdio>
    #include <cstdlib>
    using namespace std;
    struct Set_elem{ int p,size,dist; }set[30000+1];
    int Root(int i){
        if(set[i].p!=i){
            int root=Root(set[i].p);
            set[i].dist+=set[set[i].p].dist;
            set[i].p=root;
        }
        return set[i].p;
    }
    int main(){
        for(int i=1;i<=30000;i++)   set[i].p ...
  3. [NOI 01][POJ1182] 食物链

    时限:3s

    空间限制:64MB

    动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。

    现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。

    有人用两种说法对这N个动物所构成的食物链关系进行描述:

    第一种说法是“1 X Y”,表示X和Y是同类。

    第二种说法是“2 X Y”,表示X吃Y。

    此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。

    1. 当前的话与前面的某些真的话冲突,就是假话;
    2. 当前的话中X或Y比N大,就是假话;
    3. 当前的话表示X吃X,就是假话。

    你的任务是根据给定的N(1<=N<=50,000)和K句话(0<=K<=100,000),输出假话的总数。

    输入文件(eat.in)

    第一行是两个整数N和K,以一个空格分隔。

    以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。

    若D=1,则表示X和Y是同类。

    若D=2,则表示X吃Y。

    输出文件(eat.out)

    只有一个整数,表示假话的数目。

    题解

    郁闷死了……这本来是个弱题,我也想着两下搞定算了,结果从昨天下午搞到今晚才搞定。关系想不清楚就会越写越乱。

    显然并查集。把已知的每一类动物看成一个集合。当我们得到(或推断出)两只动物是同类的信息时,我们需要合并它们所在的集合。

    但是当我们处理捕食关系时怎么办呢?这就需要处理各个集合间的关系了。我这里使用了两个额外的域分别指向它的天敌和猎物集合中的一个元素(名字分别是killer和food……可见我英语很烂,给变量起名字也不在行)。每三个相关的集合构成一个关系组。我们就可以通过对这两个域的维护来处理一个集合与关系组内另外两个集合的关系了。

    注意,我们不能一上来得到一组关系就说“好,那你就是A,你就是B吧”。因为我们在得到两个关系组中某两个集合的关系(包括同类和捕食)时需要合并两个关系组,而这时很明显会挂得很惨。我们只能维护各个关系组内的关系,在合并组时才不会出错。当关系组合并时,两个关系组将合二为一,我们就需要分别合并关系组内对应集合,并且维护它们的那两个额外的域。

    在维护这两个域时需要想清楚,有没有漏掉的。不清楚就开写,只能像我一样越搞越乱。

    我把文件IO改成stdio后交poj后得到的时空开销:

    image0

    修改后还算清晰的代码:

    #include <cstdio>
    using namespace std;
    struct Set{ long rank,p,food,killer; }set[50001];
    long lie_sum,N,K;
    long root(long x){
        if(set[x].p!=x) set[x].p=root(set[x].p);
        return set[x].p;
    }
    long unite(long x, long y){
        x=root(x),y=root(y);
        if(x==y||x==0||y==0)    return x!=0?x:y;
        if(set[x].rank>set[y].rank) set[y].p=x;
        else{
            set[x].p=y;
            if(set[x ...
  4. [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 ...

  5. [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个过这道题的人,哈哈 ...

Page 1 / 2