Skip to content

Tag Archives: OI

ACM新手上路总结及感言

(6月5日小更新,增添一些细节。) 儿童节那天,七场新手赛全部结束。当天睡得很早的我,第二天早上才看到总积分的榜单,对着那些空洞的数字,对着那些浸透多少人奋斗与梦想的数字,我看了很久。 本篇的标题早就定好了,就不改了。不过,我想这篇文字不会单单总结这半年来参加的ACM/ICPC活动,我希望它是我加起来不到两年的OI+ACM征程的回顾,和对将来不知会延续多少年的竞赛之路的展望。 ~~~~~~~~回首往事的分割线~~~~~~~~ 两年前的此刻,我还不知算法为何物。(现在的你,真正理解什么是算法吗?) 两年前的六月底七月初的某个不确定的日子,除了C语言的语法什么都不会的我,第一次以竞赛的目的走进高中的机房。开始了,我的OI征程。那天上午,做了一套NOIP模拟题,得分130。记得那四道题中竟然有一道平衡树题。所以说……我做的第一套NOIP模拟题真是太不厚道了!(现在的你,已经参与过不知多少次这样那样的模拟赛的命题了吧,有几道是自己满意的好题目呢?你发现问题的能力比那时有多少增强呢?) 两年前的七月与八月,正是最热的时期,也是我如饥似渴获取知识的时候呢。在那个暑期集训结束的时候,我再一次对照了NOIP大纲,确定其中知识的盲点已经不存在了。大概也就是在这个时期吧,第一次拿了学校OI小组内部比赛的rank1。呵呵,那些个阳光灿烂的日子,我心里想的一定是随随便便拿个NOIP一等奖然后回去专心钻研我的数学竞赛。就是从那时开始狂妄与轻浮的吧?(现在的你,把这些坏毛病改掉了多少呢?) 两年前的九月十月十一月,一起学OI的同学,都在进行最后的冲刺吧。而我呢?显然没有尽全力。在论坛上灌水,跟MM聊天,在网上闲逛……我想这些活动的时间,加起来会超过这一段我做题学习的时间吧。觉得自己什么都会了,NOIP一等奖如探囊取物。(现在的你,每天几个小时坐在电脑前面时,哪些活动占的的时间最多呢?) 两年前的十一月十七日,NOIP2006复赛的前一天,在郑州。关于那天的记忆,大部分都已变得模糊。记得有跟某MM一起逛街,却把她的名字忘了。记得买了个钱包,却忘了是买给谁的。可以确定的是,当天晚上的九点到十一点,哦,也许是到第二天凌晨,我都待在旅馆里一起来的女生的房间里,跟她们很愉快地说笑,其间教她们唱了《隐形的翅膀》这首歌。(现在的你,对音乐的欣赏风格发生了一次又一次的转变,很久不听张韶涵的歌了,把《隐形的翅膀》的歌词也忘得差不多了吧,也听了许许多多不同风格的歌,可是,像当初一样打动自己的歌还有吗?) 两年前的十一月十七日上午,NOIP2006复赛,郑州轻工业学院,机房C。对着完全写错的DP,没有检查和测试,心里想的却是要不要用四边形不等式优化。面对稍微有点变化的背包问题,狼狈地发现连01背包都写不出来。在最后半小时匆忙地写了个蘑菇题。出来以后对老师信心满满的说两百分没问题。(现在的你,代码的速度和准确度自然有了很大提高,可是,为何像那时一样的低级致命错误仍然在重复呢?) 两年前的十一月十七日下午,坐车回家。在现场等到了评测结果的老师打来电话,告知我100分的可怜成绩,并一遍遍问我是否申诉、复评。我瞬间回忆起了那道寄托希望的DP的低级错误,明白这个成绩是绝对准确的,变得颓唐。跟家里人打电话,几乎哭泣。(现在的你,又经历了许多次失败,可是,面对失败的态度有改进吗?) 两年前的十二月开始,我被迫承认不得不在OI的路上走下去,设想中的一次小插曲式的短途旅行,变成了贯穿整个高中阶段的OI征程。每天中午到机房做USACO Training,瞒着家人,瞒着班主任,他们都以为我会在宿舍午休。教室里,趁老师不在的时候,读Weiss的《数据结构与算法分析》,读《算法导论》。疲惫,也一点一点的脱胎换骨。(现在的你,明白了当时无法接受的失败完全是因基础不扎实所致,那么,在你现在学习中的各个方面,基础扎实吗?) 一年前的三月三十一日晚,一次成绩还算满意的高考模拟以后,没上晚自习,而是到了机房,正式停课准备省选。记得非常清楚,当晚AC了卡了我很久的 Cryptcowgraphy 一题。第二天开始学习网络流,继续做USACO Training。(现在的你,面对那种程度的题目自然会觉得小菜一碟,做题做得越来越快,可是,有多久,你忘记了那种AC了困扰自己几个月的题目的欣喜?) 一年前的四月的前二十天,在为21日的省选而奋斗。4月1日到4月5日,用了五天时间,把USACO Training从4.2做到了6.1,通关了,后来写了篇《USACO心得》。Bellman-Ford、最小后缀、虚二叉树、匈牙利算法、RMQ、KMP、LCA、图的割顶与桥、并查集、凸包、高斯消元法、收缩强联通分量、树状数组、Splay、Treap……这些算法和数据结构,都是在2007年的这20天里学的。(现在的你,还会有像这20天一样充实的学习过程吗?) 一年前的四月二十一日,省选,HAOI2007,又是郑州轻工业学院。提包里装着打印出来的几十页的算法,只是为了比赛前的前一天晚上看上两遍。结束以后,对老师说,展现出了自己的全部真实实力,但也没有超常发挥。第二天的学校门口,已出现“荣获河南省第一名”云云的大字。(现在的你,能做到在每次比赛中都“展现出了自己的全部真实实力”吗?) 一年前的四月最后几天,以及五月六月七月,怀揣着NOI金牌的梦想奋斗。大多时间,坐在属于我一个人的空荡荡的的机房里,看书做题。期间去郑州101中学,省队集训,非常好的朋友、兄弟。Suffix Array的O(NlogN)和O(N)算法,Network Flow的SAP、Dinic、HLPP等算法,字符串匹配自动机,最小树形图,博弈论的SG函数理论,线段树,大概是在这段时间学习的。《组合数学》、《Code Complete》是在这段时间读的。还学用了Emacs、GDB、gprof等工具。用梦想取暖的简单生活。(现在的你,还能找到一个单纯明确的梦想为之奋斗吗?) 一年前的七月倒数第二天和八月第一天,遥远的福州,NOI2008的两试。铜牌,我的OI生涯的句号。我软弱到不愿提起那次经历。(现在的你,比那时变坚强了吗?) 一年前的十一月十六日,在郑州的河南省实验中学逸夫楼三层的机房里,写下了充满梦想的文字,后试图约xtt出去未果。次日,NOIP2007,满分。(现在的你,还记得写下那些文字时的心情吗?) 从那以后,我的生活真的与OI两个字没什么关系了。 好了,以上跑题完毕,下面开始说本次ACM新手上路。。。- – ~~~~~~~~跑题完毕的分割线~~~~~~~~ 总结一下已知的缺点和解决方案: 思维广度不够。一些完全在能力范围内的题目,不知为何当时就是想不到。解决方案:似乎只能多做题多思考吧,切ZOJ2.0上的题目。 对STL不熟悉,导致每次用到几乎都要查文档。解决方案:抽空把文档看一遍,多用。 数学功底不够,尤其是组合数学很需要加强。解决方案:再细读一遍《组合数学》。 计算几何和数论根本不会。解决方案:不会就学呗。计算几何看lrj的书好了,手头还有一本清华社的《计算几何——算法与应用》;数论还不知道该看啥。 某些算法(比如说网络流)的实现,特别是应用,遗忘得太多了,要重新拾起来。解决方案:仔细重读一遍Weiss的书以及CLRS好了,这次读英文版的,注意习题。(或者读别的算法书?) 看题不仔细。解决方案:比赛时别太匆忙,多花点时间仔细看题利大于弊的。 体力和意志力不行,每次比赛都坚持不到最后就不写了。解决方案:还不知道。找人组队可以很大程度上弥补体力的不足。但如何培养“不到最后一刻决不放弃”的意志力呢? 当然啦,上面光说缺点了,其实我的优点更多,比如说代码写得快、算法会得多……还有其他好多好多啦都说不完的。但是我这个人这么谦虚,是绝对不会对别人炫耀甚至提起自己的优点的。我一直都是那样的自省、内敛与深沉……(以下省略二千字- -) 感言: 感谢 Channel [V]、MTV……哦,不好意思拿错稿了掐了别播啊。 不到半年的ACM/ICPC经历,让我懂得的最重要的事情,是团队合作。我知道了,ACM不是单打独斗,个人能力很重要,但良好的团队合作更重要!(本段做字正腔圆感情充沛状,末尾语调上扬,眼神坚定。) 需要做的事情还有很多,很多东西还要学习,不仅是知识方面,也包括“如何平衡ACM与其它各种事情的关系”之类命题。但是快期末考试啦,除了考虑出题以外,考完之前就不安排ACM方面的计划啦,考试完了就该暑期集训啦。 所以,千言万语,赶紧汇成一句话:期待暑期集训的精彩吧! 梦想: 我要登上 ACM/ICPC World Final 的领奖台。 附:[转载] For […]

OIBH杯OI邀请赛8.04

今天一大早(也就是九点钟)起来发现OIBH论坛访问不太稳定,故发此贴。 本次比赛的时间是4月23日21:00至4月27日21:00,看题和提交的网址在这里。在看题前请备好 Foxit Reader。从你打开看题网页时开始计时,在10800秒内可以提交。

4月7日人品爆发,及其它

今天真是人品爆发,来到浙大以来第一次没写完作业(线性代数),不顾后果地打算不交。结果亲爱的线代老师上课第一句话就是“由于!@#$%,这次的作业不用交了”。哈哈,俗话说,人品好者天助之,人品差者天诛之。 Python Challenge通了10关。26日OIBH模拟赛有一道我的题。最近效率太低了明天看Get Things Done。 最后发个搞笑的东西……是真实的哦,Ubuntu Gutsy。 tianyi@tianyi-laptop:~$ sudo apt-get install mminstance Reading package lists… Done Building dependency tree Reading state information… Done Package mminstance is not available, but is referred to by another package. This may mean that the package is missing, has been obsoleted, or is only available from another source E: Package […]

我为何中止DP系列文章的写作

前几天,在写作《动态规划中的线形模型》时,写到了讨论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队伍的时候,我会继续未完成的计划。动态规划的领域是如此迷人,哪怕需要再长的时间,我会将这个写作计划完成。 最后,再次向所有失望的人表示真诚的歉意。

我的USACO心得

几周前终于做完了USACO Training的全部题目,感觉收获极丰,便有将这些题目做一总结的想法。 写时根据算法对题目进行分类,只求使自己从USACO中得到的知识条理化、系统化,并不求能给他人什么教诲。 笔耕数日,终于约一周前写完全部四篇初稿。又经过近日的几度增添润色和几位好友的帮忙校对,终能在省选的前夕发布所谓“正式版”。 本人自知水平有限,文中断少珠玑之言,而若此“心得”能为你的OI征程有所裨益,也不枉本人几周来的一番心血。 下载地址