Posted on 四月 14th, 2008.
要求你维护一个序列,支持两种操作:一种是查询某一个区间上的第k小值,一种是将序列中的某个数更改.经典的线段树套平衡树+二分答案.太困了,不想多说为什么这样做,想知道的自己查阅资料.
300行程序,对于我来说其实并不多,可是这是没有用Object的行数.那么估计如果用了object,350行是最少的了.这个东西也不好用object啊,除非写动态的平衡树.
其实挺惊讶于自己今天晚上的准确度,状态奇佳,这么长的程序竟然只出了两个小错(用注释//forgot!标记出来了).不过这两个小错也让我用对拍等手段调了一个多小时…
题目其实还不是很恶心的.Todo List又少了一道题了…不过同时每天也都在多题…
P.S.终于知道正确的二分答案该怎么写了…以前自己写的都太恶心了.
{ZOJ 2112; Dynamic Rankings- sqybi’s code- 线段树+平衡树+二分答案- Interval Tree, Splay}//for my winstyprogram zju2112_sqybi; const nn = 50000; mm = 10000; kk = (mm + nn) * 25; tt = 1000000000;
var cases, times, n, m, i, num, x, y, z, l, r, mid, ans: longint; ch: char; a: array[1..nn]of longint; father, data: array[1..kk]of […]
Read Full Post |
Make a Comment ( None so far )
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 ( None so far )
Posted on 四月 5th, 2008.
这道困扰了我许久的题目,终于被我过掉了…
话说当时觉得这道题太难写,于是一直没敢写…然后呢,现在Splay写熟悉了,正好FNOI做这道题,于是咬咬牙开始写.这个东西的调试实在是太恶心人了,不过还好,在用尽方法把file of integer转成text之后,终于能调试了…
写错了两个地方,一个是如果刚插入一个人有x个果冻,而要吃掉的那包也有x个果冻,这是我会把刚插入的那个人的果冻吃掉…加了个小判断搞掉.第二个是,friendID变量用重了…把一些改成了friendID_,过掉~
程序写的不是太恶心.用object写的,然后速度有些慢.于是删了object,加上inline,速度快了些.偶然删去了inline,速度竟然更快!想起了HopCroft那个问题…现在还不知道怎么回事,等着周源来问他…
{
生日快乐; happybirthday; NOI 2006
- sqybi’s code
- Splay
}
//for my winsty
program happybirthday_sqybi;
uses
happybirthday_p;
const
nn = 500000;
type
link = ^obj1;
obj1 = record
v: longint;
[…]
Read Full Post |
Make a Comment ( None so far )
Posted on 三月 24th, 2008.
变态题.做了好久了,刚开始WA,今天晚上下定决心调过,结果RE了.
和cy的AC程序对拍,拍了几十组极限数据都没错,而且我的程序比他的快得多…现在唯一可能错的地方大概就是那个又臭又长的TBinarySearchTree.delete(x, y: longint);了(名字就又臭又长…),可是还是不知道哪儿有错.如果你知道这道题有什么阴人的地方…请告诉我…
代码即使没有AC也差不多都对了,所以贴出来.希望有人能帮我看完代码…不过我知道不可能…
{The k-th Largest Group; cat; POJ 2985- sqybi’s code- 并查集+平衡树- 祝福爱德华多…}//for my winsty, for Eduardoprogram pku2985_sqybi; const nn = 200000; mm = 200000;
type TUnionFindSets = object size, father: array[1..nn]of longint; procedure init; function getF(x: longint): longint; procedure combine(x, y: longint); end; TBinarySearchTree = object root, num: longint; size: array[0..nn+mm]of longint; data, […]
Read Full Post |
Make a Comment ( None so far )
Posted on 三月 22nd, 2008.
这道题简直把平衡树的BT程度发挥到了极致…
上次写WA了,这次先是WA,然后RE201,然后RE215(这个东西…最后确认是某个节点的father是它自己,然后不断的把size增大…就溢出了),最后AC.还有比较囧的,我的程序一度无法编译…后来发现是因为数组开的太大,到了几百M.似乎object里面的这个错误检查不出?
这道题其实也很简单了,题目描述都不用发,注释里都写的很清楚了…不过考到了平衡树的所有操作.里面删除大于等于k的所有数,似乎Splay最简单…然后还有Treap据说也可以和Splay一样做,别的平衡树都要一个一个删.我这个程序就是Splay的…效率不错.
虽然AC了也很恶心…因为用了object…所以400+行…不过object在那些并查集+平衡树啊,线段树套平衡树啊,还有我一直没做的线段树+LCA之类的题目中还是挺有用的,至少过程不会混淆了.
{ superbt - sqybi’s code - Splay - delete出错: “if son[1, y] <> 0 then father[son[1, y]] := z;” 写作 “if son[1, y] <> 0 then father[son[1, y]] := son[1, z];”}{$APPTYPE CONSOLE}//for my winstyprogram superbt_sqybi; const fin = ’superbt.in’; fout = ’superbt.out’; nn = 10000000; unable = 100000000;
type TSplayTree = object private root, […]
Read Full Post |
Make a Comment ( 4 so far )