如题
About Me
-
Recent Posts
Categories
Tag Cloud
Archives
(按:本文写于NOI2007归来数日时,因为写得不完善,一直作为草稿存在后台。NOIP2007的事情没有提到,以后有时间再补充吧。) 我的OI生涯很短暂,从06年7月某个我已不记得的日子第一次以竞赛的目的走进机房开始,到07年8月2日随着NOI2007的闭幕而彻底结束,一共只有大约一年左右的时间。在这短暂又漫长、简单而丰富的一年里,我既遇到过无法接受的挫折(NOIP2006河南赛区二等奖头名)、也感受过不能抑制的喜悦(河南省选HAOI2007第一名、进入省队)、最终还是经历了难以忘记的遗憾(NOI2007仅获铜牌)。从比赛结束后,我就想写一篇像模像样的总结文章,陈述一下OI这个在我不到18年的生命中占有如此重要地位的时间的全部始末;可最终无奈地发现大部分细节都已忘却,就连大致的框架也很模糊,于是只能拣些存留记忆的片断和我自以为比较重要的给新手的建议写出来。写之前没有列大纲,可能比较零碎,这个句号的确不算圆满,希望这篇文章能给初学者一些有益的启迪吧。 我高一时选择学的是数学奥赛,当时的确用心搞了大约一年。也许有人会说这一年浪费了时间,觉得我学那么晚才开始学OI是一个遗憾,若更早开始些可能就会有更大成就。我想,OI开始得晚的确可以称为一个遗憾,但学了些数学竞赛对于OI的学习还是很有帮助的。说直接一点的例子,我那时看的线性代数大学教材就对我NOI2007时做count一题提供了很大帮助。此外,数学竞赛中培养的思维也肯定在OI的学习中起了不计其数的潜移默化的影响。数学的思维及方法在OI中的确起着极为重要的作用。所以,我建议OI新手打好数学基础:至少要将高中数学课本中的知识熟练掌握,有兴趣和能力的话可以看《组合数学》,还有就是如果你觉得自己有双方面的天赋并且时间充裕的话可以同时学OI和奥数。 在学习OI的过程中,我看的书很多,以泛读为主,较少精读。不夸张的说,市面上比较容易见到的OI教材我都有买和读,例如:《算法艺术与信息学奥赛》、吴文虎+王建德的黄皮书系列、CCF出的NOIP系列(同样也是吴文虎+王建德)、湖南师大出版社的奥赛经典系列、南京大学出版社的几本书等等。但这些书中的很多都是没必要读的,例如后面的三个系列的教材事实上选择读一套就可以,因为他们的知识覆盖面相当重复。让我受益最多的书是Mark Allen Weiss的《数据结构与算法分析》和鼎鼎大名的《算法导论》。我认为新手至少应该读一套NOIP的教材(例如奥赛经典的基础篇和提高篇两本)、读一本算法与数据结构的中等难度的书(例如Weiss的那本),学有余力的话再读《算法艺术与信息学奥赛》和《算法导论》中难度不大可以接受的部分。其实好多书都大同小异,关键是得用心看下去,第一遍读不需要逐字逐句地抠,有些内容一时看不懂没关系。 我做过的题目不算多,除了做历年真题和一些老师给的杂题外,我主要在三个在线题库上作过题。USACO Training的97道全部做完了,SGU上面做了八十多道,SPOJ上做了二十道。算起来我一共做过的题也就二三百道,跟很多人比真是差得很远。但我觉得对于NOIP而言还是不需要做很多题的,关键是选择高质量的题目以及提高做题效果。USACO的题目质量是很高的,我认为是每个OIer必做的题库,我的还是扎实的基础就都是在做USACO时奠定的。在SGU上,我做了不少弱题,感觉有点浪费时间,不过SGU上的确还是有不少有挑战性的好题的。SPOJ里面难题很多,对于准备NOI的选手来说是一个非常值得推荐的题库,我开始做这个题库比较晚,很遗憾。选择合适的题库,可以保证做的都是高质量的题目,但另一方面很重要的是提高做题效果。我个人建议每做一道题目都写一个的解题报告,可以很简短,用几行文字尽量清晰地描述出算法以及做这道题目的心得与收获就可以。
今天上午十一时左右抵达郑州,为NOIP2007。 现在在河南省实验中学的机房,老师和同学们对我太好了,还可以在这里上网。 明天就NOIP2007了,这会是我OI生涯中的最后一场正式比赛。我知道这次比赛对我真的意义不大,但我还是希望得到一个完美的成绩,希望看到一场完美的谢幕。 昨天写了《我为何中止写作DP系列文章》,同时在blog上和OIBH上发了。评论让我感慨太多。我本来以为,有些失望至极的人会大放厥词。没想到几乎所有人给的评论都非常正面,都是些鼓励、支持和理解的话语。有些话甚至让我热泪盈眶。 有人说:只有在迷茫中才能进步! 有人说:DD 的自省力让我折服了。 有人说:背包9讲我认认真真读了4遍,每遍都有新的感觉……. 有人说:任何人用真诚的态度做的东西都是受人尊敬的,更何况您在OI中有着众所周知的才华。 让我感慨最深的留言中说:沿着这条路走下去,也许您牛也会成为一代宗师。 的确,自从NOI2007结束以来,我已很久未能燃起熄灭殆尽的野心了。总是想着,随便找个大学,随便学点自己喜欢的东西,随随便便过完平淡稳定的一生,就行了。可是为什么,为什么我从未想过“成为一代宗师”? 总得有点理想的,对吧?理想高远一点没有什么错的,对吧? 为什么不能,试着,向最高处努力? 为什么不能像Alan Turing那样? 为什么不能像John von Neumann那样? 为什么不能像Edsger W. Dijkstra那样? 为什么不能像Bjarne Stroustrup那样? 为什么不能像Linus Torvalds那样? 为什么不能像Richard M. Stallman那样? 为什么不能像Donald Knuth那样? 为什么不能像Gang of Four那样? 为什么不能像CLRS那样? 为什么不能像所有那些早已成为计算机科学天空耀眼星座的名字那样? 我不相信,新兴的计算机科学已经早早衰老。 我不相信,算法的宝库已被掠劫一空。 我不相信,已经没有新的编程语言需要发明。 我绝不相信,我绝不相信有什么人注定平庸! 是的,将理想定高一些,将眼光放远一些。那些都不是真正值得作为最高追求的,离开这个国家也好,获得美好爱情也好,并非最重要的。最重要的是,思想。建立自己的思想,将它尽量长久地留存在这个世界上。也就是说,至少应该为成为“思想巨匠”、“一代宗师”而努力。 在文化路的“计算机书店”买了<Tao of Programming>,虽然里面很多鬼话,但还是值得一读,作为程序员的心灵鸡汤,作为计算机科学家的寓言。 看到了<Write Great Code>的前两卷,真是好书,写出这样一部大书的人可以一生无撼了。
前几天,在写作《动态规划中的线形模型》时,写到了讨论LIS问题的章节。顿悟一般,理解了LIS的数学本质。原来LIS问题就是这样一个问题: 一个有限集S,其中定义了两个全序关系<1和<2,用这两个全序关系定义一个偏序关系<:x<y当且仅当x<1y且x<2y。求偏序集(S,<)的最长链。 没错,这就是LIS问题的数学本质。知道了这个以后就可得出很多关于LIS及相关问题的结论。由于本篇文章并非教程,对这些结论不详加解释。 在原本的LIS问题中,第一个全序关系是“序列中x在y的前面”,第二个全序关系是“x小于y”。如果我们按照第二个全序关系对序列进行排序,可以得到原问题的一个对偶问题。即:对原序列进行排序,再把排序后序列的每个元素换成在原序列中的下标。两个对偶问题的答案是一样的,也就是说原序列中的LIS长度,肯定等于得到的新序列中的LIS长度。而对偶问题有一个非常好的性质:它的序列中的所有元素都在1..N中取值。这就带来了很多很多种O(NlogN)算法的思路,比如说可以用virtual binary tree。 既然LIS的本质是要求“偏序集的最长链”,那么就可以应用组合数学中有关的定理。例如熟悉的定理:最长链的长度等于反链的划分数;以及其对偶定 理:最长反链的长度等于链的划分数。所以LIS中那个让很多人不理解的结论就昭然若揭了。为何上升子序列的覆盖数等于最长不上升子序列的长度?因为上升子序列是链,不上升子序列是反链。 所有可以转化为LIS问题求解的OI题目一定满足LIS的数学本质。也就是说,需要用LIS的算法解决的题目,一定能找到两个全序关系,和由它们定义的偏序关系。例如那道经典的给定一些矩形造一座塔的问题,为什么按照矩形的长排序然后求宽的LIS。原因很简单,两个全序关系就是由矩形的长和宽定义的,而LIS就是要先按照其中一个全序关系排序以得到序列。 可以对LIS的数学本质进行扩展,也就是对LIS问题进行扩展,例如<1和<2不一定都得是全序关系,可以有一个是偏序关系,这个偏序关系也可能是另外两个全序关系定义的,等等……这样又可以解决更多题目,例如“三维导弹拦截”。 …… LIS问题其实只是线型动态规划中非常简单的一个模型,通过思考它的数学本质,竟然就可以得到如此多的结论,由这些结论就可以编制出无穷无尽的OI题……这让我欣喜异常。 然而,LIS的数学本质中涉及到的离散数学中的概念:全序、偏序、链,这都是我还非常非常陌生的概念。连这些概念都不敢说懂,我怎么敢说我懂了LIS问题?我怎么敢写出一份涉及它的教程? 是的,通过深入的思考,我充分理解到:动态规划的每一个模型,都可能有着深不见底的数学本质;不掌握足够多的数学工具,就不可能从本质上把握动态规划。 可我掌握的数学太少了,特别是用处特别大的离散数学,只是浅尝辄止。我深感现在的能力无法写出一份好的动态规划总结。更让我恐慌的是:竟然有那么多人,会那么仔细地,甚至带着崇拜的眼光,阅读我的总结。 由于数学能力不足,也为了避免误人子弟,我已经中止了DP系列文章的写作。今天发布的《背包问题九讲v1.1》是今年的最后一次发布。 我对期待着《动态规划中的线形模型》的所有人表示无比愧疚的歉意。你们高看了我,我目前的能力不足以从本质上把握诸多线形模型,更不足以写出好的总结。对不起,让你们失望了。 但是,要注意我说的是“中止”而非“终止”。那个雄心勃勃的计划没有夭折,只是暂时停顿了。在将来的某一天,在我自认为数学能力足够的时候,也许是在我加入某个ACM-ICPC队伍的时候,我会继续未完成的计划。动态规划的领域是如此迷人,哪怕需要再长的时间,我会将这个写作计划完成。 最后,再次向所有失望的人表示真诚的歉意。
按: 这是我在今年六月写的一篇小说。里面的四个人物的名字取自我自己和三个在网上认识的朋友。平心而论,写得真的不怎么样。 促使我把这篇原本仅限私下流传的小说发出来的原因是:我在今天得知,被我写进去的一个人物,真的与相恋多年从网络走入现实的男友分手了,而且也没有单身。我与程何都对此感叹唏嘘,我还真是一言成谶。 最后要说明的是,我把小说中我自己的名字略有替换,唯一原因是避免有人通过google我的名字就找到这里。 未写出的情诗 我把那张上面写着“专业代写情诗”的纸贴在校园的布告栏上。布告栏很高,我有点吃力。纸的下半部分用密密麻麻的小字打印着我高中时代的一些作品作为范例。我觉得这个事情还是有市场的——在我们这个以理工为主的大学里,学理工的男生普遍不会写情诗,然而不管是学什么的女生都还是普遍喜欢情诗的。 我并不缺少钱,但是能够用自己的一技之长换些收入还是很开心的。贴这个布告的主要动机大约是希望能对女朋友好些,给她买些昂贵但能让她开心的东西——衣服、鞋子、鲜花、香水之类。 我的女朋友叫刘瑜。虽然我们一起进入这所大学才一个多学期,但事实上我们已结识了两年多。我们是在网上认识的,还是在一个很俗的“讨论学习方法为主”的论坛。而后就开始在QQ上无休止地聊天,遥远地彼此欣赏。进入高三的前夕,我们一起暂时戒网,并约定考同一所大学。高考完毕,我们在这所中国北方的大学会师成功,我们发现彼此的外表比照片和视频上还要令人满意,她就顺理成章地成了我的女朋友。 现在我们已经相处了半年多。从网中走到现实自然有不一样的感觉。彼此更切肤更真实,能看到更多细节的温暖和生活的本真。虽然现在看上去感情有点不温不火,已不像起初那般热烈,但我觉得我们感情的维系还是牢固的。 回到宿舍看到了手机上刘瑜半小时前发来的短信,不知为何刚才竟没有感觉到振动。她告诉我说某店到货了Michael Crawford的原版CD,只要两百多元,她“很想很想要”。我叹了下气,默默祈祷着刚贴出去的广告能尽快带来顾客和人民币,要不然只好把准备买书的钱贡献给那个莫名其妙的Michael Crawford了。 广告的效应比我料想的还要来得早些。晚上跟刘瑜用短信道了晚安准备睡的时候,就有一个低沉的声音拨通了我的电话。那声音很稳,但让我莫名地感觉不舒服,似乎声音的边缘带着小刺。他说要买我一首情诗,给一个“只在马路上见过一面”的女生。我暗笑着这世上还真有一见钟情这么回事,约他明天在QQ上谈价钱。可这人还真迂腐得可以,坚持要明早到宿舍找我面谈。我告诉了他我的宿舍号码,就沉沉睡去,一夜无梦。 第二天是周日,昨晚打电话的那位一早就来了我宿舍。一米九的个头,进来就用粗壮的嗓音大声嚷嚷着:“我找崔天翼啊!谁是崔天翼啊?”弄得宿舍里睡眼朦胧的几位兄弟都以为我在外面结了什么仇了,然后一个个半眯着眼开始一边装睡一边等着看戏。 “你就是打电话的那个……”我一边说一边向我的室友们摆着手,示意不用紧张,这不是仇家。 “我叫顾森。中文系的。”他自我介绍道。 他的外貌还算普通,除了比我高一个头之外都没什么特别。而那句“中文系的”则切切实实将我噎了一下。一中文系的,找我这个计算机系的代写情诗,这事儿说真的荒唐了点。 “幸会幸会。我就是崔天翼。关于情诗……有很多类型可供选择。您是要唯美细腻型的?热烈奔放型的?朦胧隐晦型的?哦……或者藏头诗?就是把那个女孩的名字或者其它的话放在每一句的开头。”我快速地说着,竭力掩饰看到第一个顾客的兴奋,试图伪装得成熟世故。 他摆了摆手,似乎并不想听这些:“你先说说价钱吧。” 我一时哑口。这是我第一笔生意,在此之前我还从没想过要对“顾客”收多少钱。 “我们这一行……价钱都是公允的。情诗这种东西……你知道是最难写最耗费脑力的一种。这价格……”有些陷入混乱的我竟说出了连我自己也不可能相信的价码,“一字一元。” “好,就这么说定了。”他打了个响指,似乎对这个价格很感到满意,“那你就开始写吧,热烈一点,能打动女孩的那种。” “那……”我简直不敢相信会遇上这等好事,“那你要多少字的?” “二百字吧。”他脱口而出。 伟大的同学啊!我感谢你!你拯救了我也拯救了Michael Crawford! 顾森走了以后,我在宿舍里拿着一张粉红色的人民币忘乎所以。那是顾森给的“定金”。我本来并没有提定金这回事儿,但顾森说他给我是为了让我在24小时内把他要的情诗交货。 那么好吧,不就是二百字么。二十四小时?以我的才华和功力,这肯定不成问题。关掉手机,打开电脑,关掉MSN,开始创作。 创作、创作……坐了约五分钟后,我发现屏幕上还是一片空白。不行,写情诗一般得有一对象,要不很容易没感情的。第一笔生意千万不能砸了招牌,可得让我这位大款顾客满意了。于是,我翻出了电脑里刚结识刘瑜时写的日记和书简,开始回味那时宛如初恋的感情…… 在电脑前奋战了两个小时,写好了的稿改了又改。最后的成品一按字数统计让我傻了眼:三百多字!这怎么办呢……似乎删掉任何一句一段都不大合适。干脆顾森再来时二百元卖给他,毕竟这也是很高的价钱了。 这首诗的题目叫《未写出的情诗》。诗的思路有一点不寻常,说的是诗人梦想给自己的恋人写出一首“不朽的情诗”。倒很像我初恋时真挚的感情。 中文系的顾森同学果然对这首情诗非常满意。当看着纸张欢快地从打印机里跳出来时,他突然加了一句:“能不能在这纸上加点花体的英文,I love you什么的,做个彩色花边,再加上一行‘写给我最爱的……’” 我打断他:“那种事情你自己到外面找打印店做去,我是写诗的,不管那么多。两百块已经很优惠你了。” 顾森没再多说,扔下一百元,拿着那张纸走了。 直到现在我有了新的女朋友,又一次感受到了初恋般的幸福,我还是不知道是否应该后悔当时打断了顾森的最后两个字。那是在我生命中留下多么深刻印记的两个字啊! 如果我当时就知道顾森唇边未吐的两个字是“刘瑜”,那么也许下面的事情就不会发生,也许这场即将开演的悲喜剧还可以拉上幕布,也许我可以轻易地阻止这一切,也许我还会和刘瑜彼此相爱一年、两年……甚至一生一世。 以下情节发展的速度让我始料未及。 当我拿着两百元奔向CD店时,谁能想象此时此刻刘瑜正捧着从我的打印机里吐出的写满我火热字句的打印纸,在顾森面前做感动状。 当我终于买回了店里最后一张Michael Crawford的CD,并准备在两天之后作为情人节礼物送给刘瑜时,谁能想象此时此刻刘瑜正小鸟依人地偎在顾森的怀里。 当我故作神秘地给刘瑜发短信告诉她今年的情人节礼物她一定喜欢,并约她十四日一起出来玩时,谁能想象那延宕了很久并支支吾吾的回复是因为她已经约好了和顾森共度情人节。 当我得到刘瑜明确表示情人节那天不会和我在一起时,谁能想象我生命中第一次对深爱的女友起疑心竟然就是准确无误的。 当我两天后尾随刘瑜看见她进了一家咖啡厅,看见她面对顾森无比庞大的一捧玫瑰时无比夸张的表情,谁能想象我此时此刻的心碎。 我行尸走肉地回到了宿舍中属于我的一角,看着这曾带给我温暖感觉的一切。 桌上显眼的位置是几件刘瑜送我的小玩意儿,廉价但精致。窗台上开着我们共同的星座守护花向日葵,花盆上她的大头贴仍一无所知地灿烂微笑。 下意识地打开电脑,桌面上不住地下雪,还有穿红衣服的老头飘来飘去——那是我去年圣诞节前编的一个小程序做出来的效果。同样的雪和圣诞老人都曾飘在刘瑜的笔记本电脑的桌面上,却只有我傻傻地过了圣诞过了春节还是没有撤下来。 架子上的Michael Crawford平静地看着我,似乎眼角多了一丝忧郁。是的,每一件物品上都有她的气息,挥之不去又恍如隔世的气息。 这就是失恋的感觉吗? 以后的两个星期里,我给刘瑜打电话她不接,有时就直接关机了,短信也不回,一股人间蒸发的态势。而我心已成灰,几次看着Michael Crawford友善的面孔就想把那张CD弄得粉碎。可是,那CD是用200元换来的,200元是用一首诗换来的,而那首诗换走了我的女朋友。总结一下就是,我用自己的女朋友换来了这张CD。所以我实在不忍将它毁掉。 于是我决定试图在淘宝网卖掉它,一口价二百六十元。几天过去,浏览量倒不少,只是没人买,所有人都说CD很不错,可价格实在是太坑人了。我暗笑他们哪知道我得到这张CD的代价。 正在我颓废至极百无聊赖时,我看到MSN上传来一条信息,大意就是说CD很喜欢但是太贵了能不能便宜点。那名字倒很不落俗套,叫“梵久”。我便忍不住跟那人聊了几句。原来她是附近一个学校的女生,也是大一。她一直诉说着想得到那张Michael [...]