POJ 1765 — November Rain

Posted on 四月 12th, 2008.

话说也是攒了好久的题了…今天终于AC了.是CEOI 2003的一道题,SPOJ和POJ上都有.
一道平衡树的题目,用Splay做到了POJ Pascal组第10,SPOJ Pascal组第12.不过Nxun是POJ Pascal组第6,SPOJ Pascal第9…
题目描述么…看我和hrm的这段聊天记录:
hrm 22:51:49什么题啊？Killa.sqybi 22:52:26就是说…一堆屋顶,给出两个端点的坐标,然后任意两个屋顶不相交或者相连Killa.sqybi 22:52:31天上下雨Killa.sqybi 22:52:39问每个屋顶能接到多少雨Killa.sqybi 22:52:44雨会向下流Killa.sqybi 22:52:48就这道题..hrm 22:53:31噢。我退化了hrm 22:53:37不懂为什么用splay了hrm 22:53:45输入是什么啊Killa.sqybi 22:54:30第一行是屋顶数n 接下来n行每行四个数 分别是屋顶左右端点的x y坐标hrm 22:56:11然后呢？每一滴雨的坐标？Killa.sqybi 22:56:39哦..我忘了说每个单位长度落下一滴雨hrm 22:56:57。。。。。hrm 22:57:39那直接用面积不就知道每个屋顶接多少雨了么Killa.sqybi 22:58:02不是..雨会被上面的屋顶挡住..而且会从上面的屋顶比较矮的那边流下来
嗯,就是这样.然后呢,做法就是,从左边开始,用一条扫描线对每个线段的端点进行扫描.每条线段对应三个事件:第一个是左端点,对应线段进入扫描线上的序列;第二个是线段右端点,对应线段离开;第三个是线段比较低的一端,对应的是向下流水.然后,因为两条线段的重叠部分,一条总是高于另一条而不会改变(否则就会相交),所以可以用Splay维护一个线段的序列.最后只要先扫描一遍,同时用一个图记录每条线段的流水情况(流到哪条线段,程序中为了实现方便把边反向),然后进行拓补排序(或者DFS)就可以.
刚才在POJ上AC之后,到SPOJ上死活都TLE.而Nxun在SPOJ上AC的程序,到POJ死活都RE.最后发现了问题,SPOJ是多组数据,而POJ是一组…
{ POJ 1765; SPOJ 86; November Rain - sqybi’s code - Splay - 创建事件点,从左向右扫描,每次维护当前扫描线上所有线段的排序}//for my winstyprogram pku1765_sqybi;  const    nn = 40000;    e = 1e-6;
  type    rec = record      x, p: longint;    [...]

Read Full Post | Make a Comment ( 1 so far )

TOI 1110 — 01字符串问题

Posted on 三月 19th, 2008.

这道题是山东2007年第二次省选的题目,和这道题几乎一样的题目还在这些地方出现过:POJ 1733; URAL 1003; Vijos 1112; CEOI 99 Bugs.
看出现在这么多地方就知道应该是道很经典的题目了…
当时jl刚跟我说这道题,我就反应到了食物链那道题,但是后来jl说有mlogn的算法我就没向并查集方面想…后来发现的确是部分和+并查集,和我最开始的想法一样.算法复杂度O(m*alpha()),近似看作O(m).不过mlogn的算法没想出来.
首先,对于一个条件x y z,如果z=0,相当于转换为,对于一个只存有0和1的数组a[],a[x-1]和a[y]数组中存储的数相同.那么z=1就是存储的数不同.这里很好用部分和和奇偶性的知识解释,不赘述.这样,每次判断z,并判断x和y的关系,根据关系进行合并.用mark[x]记录树x的”敌人”(就是和a[x]存储的数不同的某一个位置–可以知道这个位置一定最多只有一个,多于一个时可以合并).
然后进行各种合并,具体方法看程序(主程序)中的判断部分.顺便判当前条件是否与之前的条件冲突.
这道题1Y,其实还是比较简单的,只不过判断的地方恶心了些,写到一半删了重写了一次…
 
{ TOI 1110; 01字符串问题 - sqybi’s code - 部分和+并查集}//for my winsty{$APPTYPE CONSOLE}program str_sqybi;  const    fin = ’str.in’;    fout = ’str.out’;    nn = 50000;
  var    n, m, i, x, y, z, fx, fy, t, total: longint;    father, mark, size: array[1..nn+1]of longint;
  function getF(x: longint): [...]

Read Full Post | Make a Comment ( None so far )