Archive for 军机处

2008年11月24日

昨天,ACM/ICPC杭州赛区以金奖(第五名)谢幕。对于Genesis队,本赛季的所有比赛已经结束,以后不大可能再在比赛中看到我们这支队伍了,希望Genesis得到的两块regional金牌以及一直以来的表现能让关注我们的人满意。

对于我已经研一的两名队友,这大约是他们最后一次以队员的身份出现在ACM/ICPC的赛场上;与高远(xgy)、杨克特(T_T)两位学长的无间配合是太过愉快的经历,学长的经验也让我受益良多。

而对于我,一名正式进入大学才三个月的大一新生,一切才刚刚开始;前方还长的路让人激动憧憬,请相信我会带来更多惊喜。

其实,这赛季能够连拿两金,取得对于我这种新手来说可称辉煌的成绩,不仅取决于全队的努力,对于我自己来说,其实不乏运气成分。这学期我主要的突破是仔细读了本《简明数论》(其实这书只有一半名副其实,“明晰”是无疑的,“简单”则谈不上),打下了还算扎实的数论基础,差不多能应付Regional中通常的数论题了,结果我们队参加的哈尔滨和杭州两个赛区正好都有数论题出现,特别是我们在哈尔滨最后才解出的B题更是我们夺金的关键。另外,在杭州赛的前几天,我匆匆浏览了《柔性字符串匹配》的后半部分,主要内容是用有限自动机做正则表达式匹配。对那本书的主题我自然是一知半解,不过倒对有限自动机有了较多的感受和认识。没想到杭州赛区的H题就是判断两个有限确定性自动机是否等价的题目。虽然没见过,但正好这几天见识了很多与自动机有关的内容,灵光一现就得出了算法,使我们队解出了第6题,也是场上解出的最后一道关键题目。

这样看来,我第一年的ACM/ICPC征程真可称顺风顺水,似乎幸运眷顾,完全没遇到挫折地走下来。当然,以后还是老老实实提高自身实力才是王道,近期打算学学Java,读读SICP之类的书。

这个学期还剩下大约一半,除了为了保持状态做点SRM以外,就不再寻求编程竞赛方面的突破了,应该多尝试点不同的内容。学Java达到与目前的C++近似的熟练程度,读SICP、Concrete Maths、Programming Pearls是必须完成的内容,如果还有闲暇就打算读读Algorithm Design以及一些AI方面的书目。最近一本《数学分析原理》让我多少发现了纯数学的美感,虽然这学期应该不大可能了,但以后还是要读些纯数学的经典教材的。物理是这学期多少令人头疼的科目,得抓紧看一下,希望能培养出兴趣。

好吧,读书去了。

Comments (8)

ACM/ICPC – Asia Harbin 2008 小结

10月8日晚的火车,三十多个小时的旅途,去往一座遥远陌生的北方城市,哈尔滨。

上火车后,惊喜地发现,我们硬卧车厢的走廊窗口下竟然有两相和三相的电源插座!可以无顾忌地使用电脑,似乎会给旅途增添不少趣味和意义。火车上,我把觉得比较有用的论文看了一遍,又对照着CD看了几章《听音乐》。

我在重要的比赛或考试之前容易滋生紧张情绪,这也是NOI2007的败笔之一。不过这次不同,一路上有队友相伴,本应枯燥的车厢里,充满欢声笑语。

灿哥通过神奇方式买到的火车票十张全是上铺,不过大家发现这种新式车厢的上铺非常舒服。更何况,在某人的下铺处有一只天真无邪可爱动人如假包换的小萝莉……这个话题不展开了,请自行YY。

T_T同学出了一些猥琐的迷题(e.g. 一只公牛和一只母牛同时踩坏了别人家的田,为何公牛主人赔偿三分之一而母牛主人赔偿三分之二?),令大家都很惊讶的,某位dd同学几乎每次都反应很快地第一个说出答案。好吧……在此我申明三点:第一,那些迷题没有一个是我之前听过的;第二,之所以我每次都能最先得出答案,我的唯一解释就是:我的思维敏捷、智商高;第三,我很天真哒,我的话讲完啦。

火车上的每顿饭都去餐车吃,虽然贵且不好吃,但毕竟是能找到的最佳选择了。这时T_T同学的母亲在德州站送上来的三只扒鸡正如雪中送炭,众饕餮很快就将那些可怜的无毛二足动物杀得片甲不留,对其二足尤不留情^_^。

火车到站时间是10日早晨5时许,一群几乎都没来过东北的人立即领教了寒风的威力。一干人等饥寒交迫地奔赴某盖头gg事先选定的车站门口的KFC,却发现人满为患无处容身。我通过手机上的Google Map搜索到了最近的另一家KFC,大家便打车前往。BTW,发现哈尔滨的GPRS网络很棒,明显感觉到比杭州的快,然而不知为何某只很拉风的iPhone在哈尔滨却无论怎样都连不上GPRS……

KFC的早餐让大家都找回了久违的饱腹感,充电完成的一干人等玩起了由gdb引进的多人纸牌游戏“盖棉被”。如果仅描述规则的话,听起来真是一个挺傻气且低技术含量的游戏:若干人轮流出牌,同时循环报数1至13;若某人打出的牌和说出的数字恰相同,所有人都需要尽量快地将手掌盖向牌堆,盖在最上面的手掌(也即反应最慢的)需要拿走所有的牌;手中无牌者胜。不过大家都玩得不亦乐乎,情不自禁高声大叫,引来了KFC MM礼貌的制止。在KFC的经历,让大家明白了一个深刻的道理(做小学生作文状):南北风俗不一样!好吧,看不懂的请略过或自行YY -___-。

打车来到哈尔滨工程大学……门口的八一宾馆报到,然后在志愿者MM的带领下入住十五元一天的学生宿舍-___-,还好后来在我们强烈要求下换成八一宾馆的标准间了^_^,偶和可爱的xgy队长gg一间哦~

10日一天都没什么安排,继续盖几圈棉被以后,一堆无聊人士围坐一圈玩起了同样低技术含量的梭哈,用另一副牌当筹码。赌博的结果是有的人(可怜的xgy gg,cmft)输到倾家荡产,有的人(就是我啦^_^,嘻嘻)成了大资本家,我赢了比翻倍还要多哦~

午饭选在某忘记了名字的火锅店,灿哥中途从机场赶来加入。相信大家都吃饱了,而且我自己认为吃得还不错,只是某人点了过多的丸子浪费不少……

下午和晚上,除了必要的赛前准备,大家仍然把时间用在了打牌与谈天之类娱乐放松的项目上。期间七个人玩两副牌的接龙还是挺好玩的。顺便炫耀下,在哈尔滨玩的很多盘接龙的分数都记录了下来,在幸运与实力的双重照耀下,dd同学是总积分的最后赢家~oh yeah~

期间值得一提的事情是,我们目睹了某欧阳极囧的脸红过程,并拍下了真相。欲知详情,请私下交流或自行YY……关键字:罩杯-___-。

10日晚上一直玩到午夜才睡。

11日上午貌似仍然是谈天玩牌。哈工程“大学生美食广场”午饭后,Genesis+gdb的猥琐男们在哈工程的长椅上懒洋洋地晒太阳,顺便开展猥琐的分手现场偷窥行动以及路过MM打分行动,期间小耗子乱入-___-。

下午试机,觉得电脑上的NetBeans还算好用,决定第二天比赛就用它了。试机期间,主办方的组织让人不能满意:每队三个人只有一份题目且不说,最不能忍受的是judge故障连连。我默默祈祷正式比赛时最好不要出现judge问题。

11日晚上,大家没有过分的娱乐,早早回到了各自的房间里养精蓄锐。我看了lrj“习题指导”和北大出版社《简明数论》两本书中的重要章节,听了贝交第五全曲,九点半安然入睡。

12日早晨六点半,醒来后的我感到前所未有的精神焕发,觉得这应该就是所谓的最佳比赛状态了。早餐中,灿哥给我们讲了若干“坚持到最后一分钟翻盘”的传奇故事。我相信听者没人想到,那天的比赛中,我们中的一支队伍会创造另一个传奇,一个毫不逊色,且注定被一遍遍讲述的传奇。

开赛半小时前进入场地,我们的装备大致如下:德芙巧克力一盒、红牛饮料若干罐、圣经一本(和合本+NIV对照)、牛津高阶词典一本、以及常用参考书一堆。

比赛开始了,共有十题,从A到J。按照一贯的读题分配:T_T看ABC,xgy看DEFG,我看HIJ。

我分到的题目都比较长,H大致看懂了,断定绝不是前期能写的题;I题意很简单,给定一个顶点的度序列,问是否存在对应的无向简单图,我觉得这应该是的经典问题,但却完全没看过类似的问题或算法;J的题意也不难理解,但可以看出,相当有大自然题的潜质。

大家把题都看的差不多了以后,互相两两交流了一下题意,没发现明显可做的题目。这时看到大屏幕上已经有四个队过题了,过的都是I。我意识到,I肯定不是难题,便专心yy之。期间xgy和我都怀疑是否只判断一下度的奇偶性就可以了,不过很快找到了反例。仿佛灵光一闪,我脑中突然出现了一个贪心构造的方法,讨论后,大家都没思路证明其正确性,却也找不到反例,于是我便上去敲了代码并提交之。

这时看到有牛队过了A,T_T给我讲了题意后,我写出前N层和的表达式给了他,他完善了一下二分答案的细节,便上去写了。写完后发现,按照我给的表达式计算的话,虽然输入不会超过六十四位整数,然而计算的中间过程完全可能会溢出,一时没有找到解决之道,只好由xgy把这个C++程序翻译成Java用BigInteger来写,交上去以后很快返回了Yes。这时已经拖了不知多久的I终于返回了,还好是个Yes。拿到两个气球的我们排名并不乐观。

在此之前,xgy给我讲了他对F的想法,我在他的基础上很快推出了完整的充要条件,但我俩都不太确定该怎么实现比较好。T_T听见后表示,如果充要条件是这样的话,那么他完全能写,因为写过很类似的题目。于是他上去用DP/递推的方式写了个程序,很快Yes了。三道题都1Y的我们第一次冲进了前十名。

写F期间,我和xgy在讨论G题,这道题的文字叙述得挺模糊的,不过通过仔细阅读加合理推测,我们很快发现原来就是一个有向无环图上的博弈问题,拓扑排序一遍再DP就行了,我上去写了以后也1Y了。当我们第4题的AC反映在大屏幕上的时候,我发现,在比赛时间过去约一半时,我们是全场第一个AC 4题的队伍,排名第一。旁边堪称全明星的清华IronGods队也只有三个气球。

这是我第一次感到情绪波动的时候,在此之前,我一直都保持着平和淡定的情绪,精神非常集中,头脑非常清醒,基本上处于巅峰状态,思考和敲题的效率都很高。然而此刻,看着大屏幕上飘扬在最上方的team53(我们的队伍编号),我出现了不应该有的过分激动以及过分自信。现在,我(多少有些羞愧地)承认,在那一瞬间,我想到了斯德哥尔摩。暂时领先造成的情绪波动直接影响到了我后半程的发挥,这也是我个人本次比赛得到的最重要的教训。

C题大概是早就得出了二分图最优匹配的算法,T_T上去写,似乎是用了令我难以置信的短暂时间就敲完了。交上去以后,返回了我们的第一个WA。我提醒T_T是否注意到船到达port以后不能再出来的条件,他意识到忽视了这一点,很快改好了,没想到仍然是WA。于是T_T打印了代码让xgy和我看。给代码查错应该是最需要集中精力的活,而我在看那份代码时却完全做不到这点,草草地、甚至一目十行地在看,怎么看都觉得没错误。很无奈的我们便想,是不是题目比较阴险必须用64位整数才可以过呢?其实赛后来看,这绝对是不必要的想法。因为当时至少有十多支队伍过了C,不少队伍都是作为第四道题过的C,且其中不乏1Y。这可以推断出,WA不大可能源于出题人的阴险,而是应该源于我们自身的问题。不过,当时的情况是,改了long long,依然WA。这期间,4题甚至5题的队伍越来越多,我们的rank一直在跌,前景非常不容乐观。看来我的缺点就是这样……处于顺境的时候容易被冲昏头脑,只有适当的逆境才能达到冷静。我再次看T_T的代码,不漏过一个字符的认真看,终于发现了程序中的低级bug。——只是注释掉了一行代码,程序就AC了。那个错误的根本原因是T_T在写那一小段时稍微有点想错了,而我从局外的角度看这段代码时,本应很快意识到这个几近愚蠢的错误,然而由于第一遍的不专心,我直到若干次WA之后第二遍阅读代码时才发现了它,这题做得不好,我至少应该承担一半的责任。

还好,虽然C题罚时比较多,在我们前四道题全部1Y的基础上,终于五题的我们名次还不错。接下来可做的题只有B和D。前者是数论题,我已经推导出了一个结果,有算法了;后者是纯粹的高斯消元而已;二者的共同点是都需要用到大数,最好是用Java来写。嗯……应该是我们队的另一个缺陷吧,我们没有人能把Java写得跟C++一样熟,所以必须用Java写的题在敲代码的速度上是吃亏的,甚至有些有关语言特性的东西还需要在赛场上试一试才知道。我们三人中写Java最熟练的xgy队长觉得B似乎更容易实现,于是便上去写。花费了比通常要多的时间,但却是严格地按照我给定的算法写出来的,没想到交上去以后WA了,只好打印出来交给我们查错,而他自己接着写D。——我想在这时我们的缺陷就完全暴露出来了:剩下两道可以写的题都需要用Java写,而赛前的训练中用Java写过题的竟只有xgy一人。这导致此时能写D的仍然只有xgy,而自己写的B还没能AC的xgy恐怕无法专心全力去写D,T_T和我在下面对着打印出来的B的Java代码YY其bug……T_T和我一致认为那Java代码十分“诡异”,表达算法时显得很不直白,但分析的结果也无法找到错误。我建议把那代码改成不那么诡异的形式再试试,大家同意了,便放下D来改B的代码。终于改出了比较清晰易懂的代码以后,测试的结果却似乎与刚才“诡异”的程序并无区别……(期间我还忍不住下手帮着写了几行,现在回忆时发现,赛场上的那几行其实是我平生第一次写Java代码- -。。。)貌似又是在我的撺掇下,把那个改完以后完全看不到区别的程序提交了,结果又是WA。这时进入比赛的最后一小时已经有一段时间了,封了board,各个队伍的排名已经不再实时公布,但从现场升起的气球情况来看,貌似已经有七题的队伍了,如果我们再不抓紧时间搞出第六题,能否拿到金牌相当未知……这时xgy继续写不知道有多大希望的D,而T_T和我做了一个相当正确的决定:我们从题意开始,对推导的过程完整地讨论地检查了一遍。期间,T_T的一句话启发了我,我发现原来是我在一开始的数学推导中少考虑了一种情况,难怪一直WA到死……我谢罪。。。还好把那种情况的代码加到程序里并不困难,加上以后就AC了,在比赛还剩十多分钟的时候,我们终于六题。

看到屏幕上的Yes的时候,我们全都激动地站了起来振臂欢呼。这是出现了一个喜剧性的小插曲,比赛的志愿者MM给我们送气球时弄错了:应该给我们的是B题对应的浅紫色气球,她却拿来了J题对应的深紫色气球。据说当时观众席上立刻一片哗然,没人想到会有队伍在比赛中把最不可做的J给做出来。周维民教授(ICPC中国区秘书长)也马上带着一堆摄影记者走过来对着我们不住地拍照。(嗯,以上文字有野史的风范,若有不确切之处请一笑而过^_^。。。)

最后几分钟的时间里xgy在敲D,不过花在这题上的时间和精力的确是比较少,加之我们不知道高斯消元在无需考虑精度的情况下会有比标准的做法好写很多的实现,所以直到最后也没能写完。至于旁边我们的Sirius凭借最后一分钟提交的D题冲至第五的神迹,我们也只有深深膜拜了。。。Orz

金牌到手的我们无忧无虑,下午我玩了会儿牌,听了会儿音乐,晚上代表队伍上台领奖(非常感谢队里的两位gg给我这个荣耀的时刻)。

接下来的时间里,Genesis与Sirius们都兴高采烈,发挥失误获得银牌的三个gdb则无法避免地淡淡失落。不过大家都知道团结勤奋的gdb实力还是相当强的,相信你们下次在成都的比赛中会弥补这次的遗憾!

其实我发现……比赛结束以后的事情我大都不太清楚了,因为颁奖结束的那天晚上起我就全身心地沉迷在一本奇书里。包括在归途火车上也一直是捧着电脑在进行一千多页的脑力激荡与思维历险……嗯,接下来我会抽空慢慢写点关于GEB的读后感的,虽然一下子很难整理出繁复的思绪。。。

哦……这次的哈尔滨之行Sirius与gdb各自也有非常精彩的小结,请原谅这篇略有些虎头蛇尾的文章吧,这五千多字已经写得我要吐血啦。。。有什么脱误遗漏错愕指出请指出,我一定修改。

好了,下一站杭州,在自己家门口比赛,相信通过对哈尔滨之行的总结,我们会越发完美。Genesis加油!

Comments (16)

近期读书计划

确定了浙大今年有“新生预备学习”的项目,可能很快就要去杭州上学了。在此之前要读完下列书目。如果时间不够了可以把最后两个删掉。标星号的要做较详细的阅读笔记。

张五常《经济解释》*
陈鼓应《老子注译及评介》*
《什么是数学》*
罗素《西方哲学史》
《费曼的彩虹:物理大师的最后24堂课》
陈鼓应《庄子今注今译》
《王小波作品集》(五册:黄金时代、白银时代、青铜时代、黑铁时代、理想国与哲人王)

还要在三月底之前在ZOJ上做300道以上的题目才有可能进校集训队。>_< 很繁忙啊……

Comments (6)

省队集训总结及比赛策略及近几天的安排

坦率讲,并没有在省队集训中真正“学到”什么东西。最大的收获是在九场测试中得到的临场经验,以及Emacs的学习和应用。

遇到会做的题,应该用迭代开发/代码复查/生成数据等各种方法保证正确性。Coding也不宜太快,毕竟NOI的时间是充足的。

遇到大致知道方法但是写起来很麻烦的题目,不妨先花几分钟写一个Brute Force的程序放到那儿,然后在埋头Coding。那种麻烦题目一定要把思路完全理清楚了再去写,千万不要写到一半写不下去了,那是最得不偿失的。

遇到暂时想不出来的题,不用慌,慢慢分析,或者从一个垃圾程序开始慢慢迭代开发。相信自己的实力。

遇到一看便知很麻烦很麻烦的题,大胆放弃,但写个Cheat程序还是必不可少的(至少可以稳定情绪)。

注意先写程序后优化。程序的每个重要版本都要备份一下,例如第一个可以编译的版本,第一个过样例的版本,某次大改之前的版本等等。

在准备在程序中大量加入调试代码之前,先看看变量、数组的声明是否正确,看看有没有弱智错误。

近几天的安排:

任务一,每天写二至三道NOI难度或略低的题目,保持状态。

任务二,精炼一下几个(不太常写的)最基础的东西的代码:quicksort、heap、highprecition等。

任务三,打印自己写过的文章/代码看。

就这样吧。

Leave a Comment

省队集训总结

See Also:
http://blog.sina.com.cn/xjoxjoxjo
http://blog.sina.com.cn/marforever

7月11日

1. Emacs+GDB的确是正确的选择。
2. 代码复查是好习惯。
3. 双向搜索、或者说折半搜索的思想。(第三题)

7月12日

1. 越是简单的题,越是需要用DataMaker、代码复查等各种手段反复查错,保证AC。例如今天的第一题,写错太不应该了。一定要警惕在某道题上花费时间太少的情况。
2. 出现访问段异常时,如何在GDB中定位到异常的那一行?
3. 第三题那个AC程序的随机化——不断缩小随机的范围,相当神奇。

7月13日

1. emacs -nw 更好用。
2. 第三题文件名写错,300分变成200分,攒RP了。

7月14日

1. 第一次见的经典网络流题AC了还是很高兴的。Dinic果然无敌。
2. DP题还是要先慎重确定方程无误后再下手。注意贪心(第三题)。

7月15日

1. 第三题绝对是太贪了,考虑太复杂。不过也怨题目没有给出更详细的数据范围。否则我就很可能Brute Force了。
2. 第二题独立想到,图论基础还是可以的。
3. 第一题策略严重不当,想的二分答案,等二分答案的所有步骤都写完了才意识到不能直接二分(也没想到yxy那种找单调性的上下界然后二分的方法)。
4. 强调一下:先把算法想清楚再下手。
5. 细节的确决定成败,第三题明明想到了Fibnacci数,也想到了那个唯一分解的定理,但由于错误的“负Fibnacci数”的想法,导致满盘皆输。只是一个小小的偏移量就可以避免麻烦的负数。真是心有不甘啊。

7月17日

1. 多日以来攒的RP终于在今天短暂爆发,拿到了第一个真正的300。不过就像别人说的那样,这导致我今天的收获远不如前几天。但也不一定,前几天得到的是“教训”,今天得到的就是“经验”了,例如:高度模块化(大不了最后再改成inline、define),坚持迭代式的编程(滚动数组、最优性剪枝、常数优化之类的东西都一定防盗最后再搞)。看到其他几个人的代码风格真是惨不忍睹。
2. 你以为会个最短路、会个网络流就是会图论算法了吗?看看Graph-Theoric Algorithms吧。太优美了,真的。
3. Emacs学习告一段落。GDB还是做不到熟悉的静态调试那样得心应手。

7月18日

1. 第一题正确的贪心策略没有想到,用加卡时的乱搞得了一半的分数,还是很满足的。
2. 第二题做过的题20mins就写AC了,就应该这样。
3. 第三题题意太不清,忽略。

7月19日

1. 提交答案题。出现一个重大失误,在算后面的数据时由于编程序的失误把前面已经算出来的解给覆盖了……看来以后要把已经算出来的解妥善保存好。还有就是对于今天这种很可做的提交答案题,要记得分配两个小时左右的时间。
2. 交互题浪费了太多时间,似乎还是因为没有完全想清楚就开始编程的缘故。(竟然是60分而且跑出了5个极限数据中的3个?我也很惊讶……)
3. 如果有巨BT的模拟,像今天第一题那样的,放弃是最明智的选择。

Comments (4)

计划7.11-7.20

以学习为主。知道自己来这里干嘛的。

上午仔细做题,注意时间分配,练Emacs,练GDB。

中午另安排。

下午要把上午的所有题都搞清楚,除非公认不可能搞清楚。

晚上总结一天。

注意珍惜时间。

根据明天的情况再细化。

Leave a Comment

开始做SPOJ

对于我这种人来说,如果想让我踏踏实实的进行一个长期计划,最好的办法就是把这个计划让全世界的人都知道。比如说我准备做USACOSGU的时候,就专门各开了一个发布题解的blog,这样我做了多少题目老师、同学、朋友甚至父母每天都能看到,我也就一点不敢松懈了。现在USACO征程完成了,SGU之旅做了80+(窃以为Chapter I/II中最有价值的题目都做了),于是我又打算做SPOJ了。

SPOJ真是一个非常非常好的OJ,网站的架构和理念非常先进。超级无敌的多语言支持就无需赘述了。还有一些很贴心的功能,比如说它会保留你每次提交的源文件,可以自己下载自己以前的代码,而且若选择了邮件通知功能,还会把每次提交的代码作为附件发给你。另外像调整宽度、换肤、提供每题的PS/PDF等小细节都很令人赞叹。这的确是我看到的最完美的OJ系统,在上面做题的确非常舒服。

好了,说了这么多,只是为了督促自己努力做题。除了学些新算法(其实需要学的已经为数不多)以外,更重要的是训练自己的代码风格变得严谨,彻底改变以前那种狂提交的做题方式,提高一次AC率,顺便还能给这个题解很缺乏的OJ贡献一份尽量丰富的题解。考虑到我的blog已经着实不少,就不再为这个OJ新开blog了,请通过这个页面监督我的做题情况!

Comments (5)

NOI训练近期计划

近期必须要提高效率。用二至三天的时间详细记录时间表,以提高效率。每天早计划晚总结。

必须要做的是把Linux装好,Emacs和Vim都试试。总结一下自己用Dev-C++时需要的全部功能,然后用某种编辑器全部替代了。GDB也可以试试,如果真的很爽的话就用Emacs了。Vim最无奈的就是编译了,感觉上比较好的解决方案还是写makefile,这样的话多Tab要搞清楚。

算法方面,一个必须要掌握的就是块状链表,考的可能性很大,所以说完全可以花一两天甚至更多时间仔细研究仔细实现,除了NOI2005那个题以外还得找别的练习一下。网络流再写一两遍relabel-to-front,感觉一下,有空的话写个HLPP也行,Dinic写不写似乎都没关系,毕竟距离标号已经写得很熟了。

平衡树是另外一个大重点,一定要多练些麻烦的题练熟了。把递归Treap和Buttom-Up Splay要练到十分钟/十五分钟能默写的程度。

字符串处理方面。Trie图的相应的那几道题目做了也就没什么需要多说的了。最好搞懂“扩展KMP”是什么东西。后缀数组,如果遇到了非得O(N)的题再考虑学Skew Algorithm,否则就把nlogn的好好掌握就行了。

做题的话,SGU应该在一周内告一段落。下一步就去SPOJ攻难题吧,也可以照着网上的题目推荐内容做些POJ/Ural之类的补充。另外发现TopCoder的题目很不错,对照着题目/题解欣赏下似乎很好。

效率,一定要注意效率。珍惜时间,绝对不启动浪费大块时间的娱乐计划。

Leave a Comment

2007六月计划

除了OI,没什么其它需要计划的。

六月的主题是:学习新数据结构与算法,做NOI真题,夹杂着要做一些SGU和SPOJ上的好题。

新的数据结构与算法包括:

Dinic算法(网络流):NOI Profit等。
Stoer-Wagner算法(最小割):UVA 10989。
Trie图(字符串自动机):SPOJ WPUZZLES、POI #7 Virus、Ural 1158、Ural 1269。
块状链表(链式数据结构):NOI的题。
后缀数组的Skew Algorithm。
后缀树(optional)
计算几何(optional)

NOI做2000-2006年所有题目,每周2-3套,写总结。

娱乐不可无,但绝不可多。订阅的RSS看看,jandan看看,某天完成的东西蛮多也可以gaame一下。原则是娱乐量要与工作量正比。

六月很关键,不用说也应该知道。几乎可以认为,成败在此一月了。

Leave a Comment

近期要实现的数据结构与算法

从未实现过的:

Dinic算法(网络流):NOI Profit等。
Stoer-Wagner算法(最小割):UVA 10989。
Trie图(字符串自动机):SPOJ WPUZZLES、POI #7 Virus、Ural 1158、Ural 1269。
块状链表(链式数据结构):NOI的题。

以前实现过,但是需要活用的:

线段树的题目:PKU 3225。
平衡树的题目:NOI的题。

6月份的前两周把它们做完。

Leave a Comment