ZJOI day2 Bless all

马上就要ZJOI day2了…大家加油…

还是那句话,好好努力,不要有遗憾就行了.

 

PS:我赶完了可持久化数据结构的讲课ppt,残念的是基本就是我的hw2的论文,大家看过的就不用来了.

 

主席求轻虐T_T.

some exercise of persistent data structures

在我CTSC滚粗了之后,本来想天天喝点小酒消消愁的,结果发现还得去ZJOI day2,讲课也已经排好推不掉了…

于是我讲的是可持久化数据结构…

正好把以前想的一些例题贴出来:

1.QTREE的可持久化版本:修改一条边,询问2点间边的最大值,回到第i个操作结束的时候.必须在线

2.n*n的矩阵,每次询问一个子矩形内部第k大的数,n<=100,询问数<=1kw,时限5s.必须在线.

3.SUBSTRING的可持久化版本:给一个串,支持往后+个字符,询问一个串出现次数,回到第i个操作结束的时候,必须在线.
总长度<=20w,操作数<=10w,时限3s.
4.BZOJ 2787

嘛…有时间可以先看看…反正也很sb…到时候也会讲…

CTSC行记

飞机晚点了1个多小时,没事情做就写点行记吧。

现在说起来感觉很sb很脑残,不过考试之前对自己还是挺有信心的,考试前TC CF 互测状态都不错,感觉说不定有希望进队 。来了之后感觉心态也挺不错的,跟liuhx 住一间房,皮包骨头给雄壮无比的跪了。

也不为自己的失败找借口了,就吸取点教训吧,自己考场能力还是不够啊,或者说是太不够冷静了吧。第二题做了半天也做不出来,就去死磕第一题,结果没调出来,现在想想我都觉得是不是当时脑子进水了,之前互测状态不错自信过剩以为自己肯定写的出来,结果当然就挂了。残念的一试分数就惨不忍睹了

之后感觉也没什么希望了,不过人就是不见棺材不掉泪么,还是想着二试翻盘什么的,结果二试题目发下来一看么,就知道没什么希望了,最后d8,感觉也是凑合着过了吧。

其实我或许是个傲娇么,考前觉得无所谓的吧,考挂了还是非常的伤心,就有一种心里少了一片的感觉,遗憾么,也还是有大片大片的吧,之前跟我妈说无论进不进高三都去学英语不搞oi了,现在想想还是放不下啊,傲娇就傲娇吧,争取明年能有个好结果吧。

回顾一下我的OI生涯,好像走的顺过头了,wym说他幸运E,我感觉我幸运至少有B吧,虽然不是在强校里出生,但是各个比赛都进行的很顺利,正式比赛里似乎还没有拿过银牌(就装个小B吧),现在受点打击也是好事吧,至少让我明白了很多自己的不足之处吧。

不过呢,我想人活在世界上,只有得不到的东西才是最美丽的东西吧,遗憾永远比满足的时间更加铭记在心, 我想如果明年能进队的话,会比今年进队开心很多吧,就算没进也没关系。

这一年我算是认识了不少人,交了很多朋友,竞赛生可能很大程度上跟高考生不同,是一种个体性的生物,一个人做各种各样的事情,就是所谓的geek精神吧,以前我也有点孤僻的吧,但是现在我开始觉得能有个别人在身边,能够与别人互相穿过对方的人生,是一件非常美好的,非常重要的事情。 

最后祝贺进队的四位同学,尤其是超哥跟gyz,认识了都2年多了, 基友们都走了我感觉有点寂寞啊

滚粗了

RT

RT

RT

(度娘文章过短你妹)

(真是想笑啊,还以为自己很NB,其实就一SB,明年再来吧)

挂了就是挂了,本来想找点什么出毛物理题啊之类的借口,也没什么意思,

嘛,看开了看开了,明年tourist退役了说不定还能混个奖杯什么的(大雾)

我就算了,感觉我很对不起wqs…

xujie纯爷们啊……二试题目太水翻不了盘真是尼玛…

另外cong lich zpl ayq gyz 进队.

homework2 2012 by wjmzbmr

http://115.com/file/e77aykwi

这是我hw2的作业.

主要的内容有WC题解,互测自选题题解,两篇自选题解题报告和一个可持久化数据结构的研究报告.

尽管我认真的进行了多次校对,还是可能有错误,请轻D T_T.

集训队互测总结

LZ先去喝口翔…

(我会说我是骗经验的?)

 

嘛..集训队互测终于结束了,我就简单的总结一下吧.

首先我感觉现在的OI真心是比谁挂的少,只要做到傻逼题会做,难题骗点分,也不要挂题,就基本能混的很好了.

还有就是心态的问题,我感觉我现在心态非常不错,能进就进,不进打gal去,压力毫无.也许这样的心态才是最重要的吧.

另外就是比赛策略的问题,我感觉我的比赛能力还是不够成熟,还是会发生某题题目耗时过多导致悲剧的情况,一般来说比赛之前都是要计划一下比赛的时候要做些什么的,一开始的时间最好拿来想一下每道题目然后列个能得分的表.

最后就是对拍的问题,我感觉在互测中由于我勤于对拍,所以正确率非常高,对拍的话无论是时间空间正确性都要拍,这个是很关键的.

 

(本来是想写详细的总结的,残念的是很多比赛的细节给忘光了)

 

说到稳定性,我统计了大家的标准方差,可以看出gyz的稳定性是最高的,是0.1747,其次是ayq(0.1857),再后面是我(0.1890),最高的是wqs(0.3110)…可以看出wqs的战斗力跟妹子密切相关..

 

由于详细的写不了了,就换成一些吐槽吧.

1:某校原题团给我送了3个rank1,导致我初期就混的不错,最后那人的比赛最后一题我因为mac和windows下面卡时函数的效果是有差别的!结果一题分数跪光就跪了.

简而言之mac下面CLOCKS_PER_SEC = 100w,但是win下面是1000.

2:似乎流行坑队友,某校大家互相坑的很开心……

3:要自己分高的关键是要么把题目出容易,要么出很高的部分分…

4:某人出神题虐人,由于自己在自己的比赛的分数是平均分/最高分,TA的这项分数就最低了.

5:我总共混了5个rank1,有一场是wqs出糟糕水题赛不算的话,其它4场都是HN的人的比赛…..

ZJOI 2012 Round 1 mrx 详细题解

有人说我那题的题解过于意识流。。。。

于是我就看了一下。。

发现没有看懂。。。。。

发现没有看懂。。。。。。

于是我来写一个详细的题解。。。

 

首先,我们倒过来计算空矩形的数量,答案就是 矩形的数量 – 空矩形的数量。

那么,我们按行扫描,每次计算底边在当前行上的空矩形的数量。

那么实际上这个的答案,只跟当前每列,往上能伸展多少有关。

不妨考虑是这样的图形。

让我们考虑如何计算答案。

由于底边已经确定了,那么我们需要选择的就是上边界和左右边界(也就是左上角和右上角)。

继续观察这个图形,划分一下,可以发现它能够看成一个树形结构。

注意到,左上角和右上角,必然都在划分过之后的同一个矩形块中!

设划分出来的矩形宽度为w,高度为h,那么在这个矩形中的答案就是C(w+1,2)*h。

在树的节点中维护它所有子孙的答案和。

由于这个是一个树形结构,我们可以用树来维护,同时因为数据是随机的,故树的高度是logn的,这个可以用随机笛卡尔树高来证明。

接下来我们是在一行行扫描,所以得考虑如何维护。

如果下一行是空的,我们只需要把最下面那个矩形,也就是树的根,的高度+1就行了,同时更新根的答案。

如果下一行中有障碍物。

比如在第c列。

画一下图可以发现,整棵树,被顺着第c列,切成了两部分。

我们只需要在切树的同时,维护树的结构和答案即可。维护的复杂度跟树高是相同的,所以总复杂度就是nlgn。

具体的代码我已发在我的网盘,我自认为写的还是挺可读的。

 

 

Page 2 of 5412345...102030...Last »