Skip to content

Tag Archives: NOIP

七月的第一天

前两天期末考试结束了,一下子就感到满心的轻松自在。虽然逐步公布的成绩不断刷新着低分记录,但至少担心挂科的危险已经没有了。不愉快的事情几乎已经遗忘过去,我再次表现出了不想记得的事就能迅速抛到脑后的优良品质,没心没肺惬意地活着。 考试完了以后,就一直在准备家教的最初几节课,还在非常认真地做ppt:简要介绍OI、讲解初赛知识、C语言的Hello World……很繁琐呢。听说大多做一对一家教的人都不做ppt直接讲的?反正我是打算要做就做到极致和完美。也就是说,我打算做的工作量,基本等于自己写一本完善的从零开始的NOIP辅导教程。不过,那不是我一直想做的事情吗?教育是高尚的事情。虽然还没正式开始,发现自己已经很热爱这件事情了呢!后天去第一次试讲,我知道那会很成功的。 这学期上的C语言课程,期末可以编写“大型程序”赢取额外的加分。我编了一个“表达式解析计算器”,可以完成基本的四则运算、科学计算等,还会绘出表达式树(调用graphviz),被助教评为95分。有兴趣的可以下载来看一下,包含完整的源码、Win32可执行程序以及文档。其中我的代码没有什么license,可以拿去任意使用。 放假了,blog 的风格会转为少量多次的即时更新。

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 […]

在郑州

今天上午十一时左右抵达郑州,为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>的前两卷,真是好书,写出这样一部大书的人可以一生无撼了。