我在OI中辗转的这千百天

今天是2017年12月16日，距离NOIP2017结束已经过去一个多月了。我想写一篇文章来留念一下我在OI中辗转的这千百天。

0x01 初识OI

我最初知道NOI系列赛事是在初一的时候。

小学到初中有在跟着思明区青少年宫的老师学电脑机器人，当时在班上有个比我大岁的朋友，他刚上高中，知道了有NOIP这个比赛，后来他拉着我学Pascal入坑了。

那段时间他带我入门了Pascal，水平大概达到了会写校门外的树的程度，后来由于我的时间关系和他的时间关系没有继续往下学。当时由于周末还拿出一天上电脑机器人的课，所以也没有太多的闲暇时间。

后来到了NOIP报名的时候，我问了我们班主任能不能我们学校找个信息老师挂名去参加NOIP，之后便没有下文了。

其实现在想来，当时的水平甚至连通过普及组初赛都不够的。那个时候我的水平仅仅只是会用Pascal写入门难度的程序。并且那个时候的我也不了解算法和数据结构，对于计算机的学习处在一个以自己玩为住的状态。当时搞机器人，搞单片机。搞Web开发，搞C#、VB、易语言写点小程序。记得小学六年级的时候写了个控制飞机躲避障碍的游戏和弹球游戏就觉得自己很厉害了，现在自己看来这些东西真是小儿科。正如我当时写的弹球游戏需要考虑的圆以一定的速度和角度与直线碰撞的问题，我根本不会判，当时易语言有个组件叫画板，基于DirectPlay，判断物体碰撞只要设置速度和角度物体就会在屏幕上移动，碰撞的时候会调用一个事件，根本不需要像我写OI的计算几何题目一样去考虑各种东西，所以我当时根本没有想过要学习算法和数据结构，不明白它甚至可以帮忙升学，初中阶段也就把这个事情搁置了。

0x02 高一的NOIP2015

由于一直对计算机感兴趣。初中的时候希望中考能考上一个OI强校成为了一个目标。然而不幸的是，中考的时候考的很差，高中来到了厦门集美中学。

高中的第一节信息课，信息老师就在问我们全班同学有没有人知道NOIP这个比赛，我记得当时全班就我一个人举了手，然后和老师交换了联系方式，周日开始在学校上课。

当时我们学校OI班上大概有20个人，招人方式几乎只是问问谁感兴趣谁进来。其中还有个高二的学长和高二的学姐都是之前电脑制作拿过奖，就被我们老师拉去参加NOIP了。显然这和OI不是一个知识体系，毕竟我们也是老师带的第一届OIer。但不幸的是，初赛结束之后就只剩4个人参加提高组复赛了。而初中普及组的初赛通过人数还是挺多的。

后来自然就到NOIP2015了，然而当时什么算法都不会，只知道C语言的基本使用，也不会STL，甚至连搜索都不太熟练。最后Day 1T1做了出来，剩下的题目要么打个搜索，要么打个特解，要么打个输出random，最后得分150。当年恰逢CCF取消省三等奖，福建省计算机学会和省教育厅自己发省三等奖，当然这个奖自然是毫无卵用除了免信息会考。对我而言也是一个信心上的鼓励。

并且我也听说了福师大附中的hzwer，高一拿省三，高二省一，省选R2翻盘最后进队，最后NOI Ag PKU本一。当时也梦想着自己也能走这样的路，然后好好学了一段时间的一本通和刘汝佳的紫书。但最常见的问题就是我遇到了一些不理解的地方靠着自己上网搜索也找不到详细的解释，还经历过明明算法是没错的却一直WA查不出原因的的状态。感觉自己靠自学的上升遇到了一个瓶颈。毕竟身在弱校，没有厉害的学长，也没有厉害的老师，一个人靠着兴趣自己努力地从网上和书本找资料来看确实很困难。但也就这样坚持了几个月。

0x03 环境的转变

由于NOIP2015拿了我们学校最高的分数，后来老师不在的时候就经常让我给其它同学讲课。我越来越意识到在这样的环境中难以提升自己。在我高一下学期大概过到一半的时候，我通过一些朋友关系联系了当地一所强校的老师，然后去跟班学习，然而跟的是当时初二的班。

后来才知道原来就算是搜索也能用各种方式优化，比如双向广搜，A*，原来DP不一定是数组和for循环，还可以状态压缩，还可以树形DP，还可以斜率优化，原来还有各种各样的算法，原来解关灯游戏还有多项式时间的高斯消元做法。

由于当时玩心比较重，虽然学了很多东西但是代码能力依然不强，自己训练的时间也比较少。再加上当时班上的同学还在初中，大家都没有一种非常努力地去冲OI成绩的态度，我也便随波逐流，失去了和我同龄人相比的危机感。尽管取得了很大的提升，但还不足以稳拿省一，更不用提去考省选了。

0x04 NOIP2016

NOIP2016考前还在自学线段树和LCA，用的还是最难写也效率最低的DFS序+st表的RMQ，但是只打了个模板题，没有做那种需要好好思考的题目来锻炼能力。但我当时依然在安慰自己至少我会打模板了，万一它考个裸题呢。

很快到了NOIP2016考前一周，但由于9月份魔读OI到10月份月考成绩退了不少，自己在班上又是学委却在那段时间经常欠作业被批评。于是10月份在魔读文化课。现在看来这是我高中做过的最错误的决定。更加不幸的是，当时在班级里被空调吹感冒了，NOIP2016那两天发着烧考试。记得当时考试带了4瓶水进去由于一直冒汗全都喝完。觉得当时在考场里整个人完全没有智商可言。

那年考场被安排在师大附中，然而师大附中的那间考场却成为了我心中一直挥之不去的阴影。

Day1的时候考完面对那么难的题目心态爆炸，以为自己今年NOIP省一无望了。当时T1模拟水过，T2暴力分25。T3一直想写个DFS搜索，然后考到剩余半小时的时候依然是WA，最后只好把部分数据m=0的交上去。由于floyd有个地方写错了，m=0的测试点还被卡掉了一个，最后Day1只有149。

到了Day2，由于Day1心态爆炸，再加上对题目难度的误判，按照D1的难度我觉得这天能做出T1就不错了，便决定要把T1先拿下再去做别的题。我写T1的时候发现是个杨辉三角，但是由于这道题我查询的时候做了个前缀和，我一直以为是我把前缀和当查询输出了，然后调了半天，一直在那对拍，最后没用杨辉三角的做法，60分。剩1个小时的时候才来写T2和T3，T2写了个优先队列然后一直CE，现在回想起来似乎是因为当时题目输入有个q，而我开的优先队列也有个q，然后冲突了。但是调试的时候并没有时间去找这个错误，最后15分钟的时候非常快地写了一个每次排序的纯暴力，又因为时间计算的时候忘了-1，最后T2、T3爆0。

考完之后回酒店拿起iPad下载愤怒的小鸟，自责T3那么简单的搜索就能60分的题目为什么没去打。

NOIP2016考完心灰意冷，但是也下定决心明年无论如何也要拿到省一。毕竟我已经用光了所有的机会，只剩下明年这最后一次了。

不过NOIP2016成了集美中学OI的一个顶峰，提高组有个初二跟着我们当地一所强校学习的大佬拿了一等，普及组也有一个初三的女生拿了一等。而我却只拿了一个二等。

0x05 意识到自己有多弱

后来2017寒假的时候去省冬令营玩了一圈。

最开始我们教练还认为我没必要去，毕竟确实以当时的水平去考省选是没有可能进队的。但我当时执意要去，我想去看看我的同龄人已经学到了什么样的水平，我想去看看我要达到他们的水平我还需要学习多少内容。

这次冬令营也在师大附中，和我NOIP2016的考场在同一个学校。于是我又来到了那间留着我NOIP2016悲伤记忆的考场。结果发现Linux系统没有受硬盘还原卡影响，我又在NOIP2016考试时用的电脑上发现了当年的悲伤记忆。

基本上每天的上课都是懵逼状态，所讲的内容大概只有10%能理解，但也学了不少东西，训练了思维。每天的练习题也都是打暴力，觉得经历了那几天我的搜索水平有了一个质的飞跃。包括到省选一试的时候也是打暴力。

最后的省选一试也就在省冬令营之后，我再次被安排在了师大附中的那间考场。

可是最后，却因为我没看清楚程序提交格式，每道题建了子文件夹，省选一试直接爆零。

后来度过了心灰意冷的几个月，学习了一些计算几何、线段树、网络流。

当时在学线段树的时候还见到了POJ 2482这道题，学了下线段树和扫描线花了一晚上把它AC了。之后去翻译了一下题面，并且改成了一维，出成了洛谷P3353。

高二下的学习也日益繁重，我也不再有太多的时间花在OI上了。

暑假的时候学了下很基本的状压DP，把历年的NOIP题目好好做了一下，把题目里需要用的相关算法学了一遍，又把同类的题目做了几道，然后开学就没怎么码代码了。

0x06 NOIP2017

高三一轮复习阶段自然是更加繁重的。这个时候还在准备OI的人往往都是已经在NOI2016签了大学的大佬，只为给自己学校增加省一数量的选手。

初赛考前我又一次在机房中给我们学校的OIer上了一节课，由于今年福建省不允许初中生参加这些学科奥赛，我们学校的OIer数量一下子少了很多。但是我很快发现他们的水平甚至还没达到我高一时候的水平，最后的结果相信大家也猜到了，我们学校除了我没有人通过NOIP2017初赛。

初赛考完之后周末就没怎么动文化课的作业了。考前最后一周文化课作业基本都没动，甚至同学在复习期中考的时候我在拿着纸和笔模拟我学过的所有算法。后来到了NOIP2017前两天，心态放的很平和，想着今年应该稳了。

考前还算了做了一个计算，NOIP 2015的时候我的准考证号是FJ-0220，220%3=1，最后拿三等奖，2016的时候准考证号FJ-0002，2%3=2拿二等奖，2017的时候准考证号FJ-0075，75%3=0，那应该能拿省一等奖了吧。（笑

今年被安排在福州三中考试。中午路过三中附近的时候就见到了他们的校服，觉得比厦门统一校服好看多了。

然而报道的时候却发现自己袋子里的考生须知是Windows的，结果发现原来是我们老师没有把竞赛环境回执发到正确的邮箱，结果变成要用Windows考试。

而Linux考试自然是有很多好处的，环境是纯正的NOI Linux，与评测环境完全一致，可以避免许许多多的问题。比如没加cstdio导致CE就可以在考场上发现，文件名和头文件大小写打错等等也能测试出来。更重要的是有个好用的Shell，自带diff、gdb等工具。并且Linux调试遇到一个死循环的程序还可以按Ctrl+C暂停，然后用gdb单步执行看问题出在哪。

于是那天下午我一直在考场待着，看看Windows下有什么好用的工具可以用。福州三中装的系统还不错，自带notepad++。然后我就开始码线段树，一个我几乎没有一次写对过的数据结构。我不曾记得那个下午我在使用cmd的时候多少次把dir打了ls，多少次g++命令没加-m32，甚至还有许多次gdb也没打gdb32。还研究了好久如何配置notepad++，就像第一次接触vim一样的感觉。不过最后我依然没有打对那个线段树，拿U盘把程序拷走回宾馆。

那天晚上本来打算在西湖散步的计划被突如其来的变故打乱，我只好去适应Windows下gdb的使用。果然发现一个大问题，单步执行的时候经常出来一大堆cygwin的文件，后来查了各种资料。顺便也调完了下午打错的线段树，只是因为一个L打成了R。

之后经历了一晚的不眠之夜，不是因为第二天重要考试的紧张而是因为这家宾馆旁边是一家夜店。我最后一次看时间已经两点了。

之后Day1还算比较顺利，刚看到T1我第一反应是完蛋了，过去D1T1随便AC，今年怕是只能拿暴力分了，我先是写了个exgcd然后感觉不对。此时距离开考已过去10分钟，于是我的思路变成了如何算出这两个数在某个数之后一直能组合出来数字的最小值，毕竟看数据范围这要么是log n算法要么是O(1)算法。想起来之前学过欧拉函数，对于质数phi(x)=x-1，我就猜测这两个互质的数会不会有类似性质呢。我就打开了样例2，发现似乎可以吻合(a-1)*(b-1)-1，然后题目已经给出了a、b互质，并且都大于1，就不存在无解的情况，我大胆地手动对拍了几组数据发现居然都成立，就这样大胆地写下去了。此时距离开考20分钟。想起自己这是第一次在OI题目中针对正解写这样的O(1)算法。

T2看起来很难，我就先去看了T3。本来一眼看以为是简单的最短路计数，结果发现不但不是而且还要判断0环问题。我还去想把费用流改一改，我考场上还想到Tarjan把0环缩点走过去直接输-1，然而并没有想到如何实现，却花了很多时间在那乱搞，于是打了个SPFA预处理+DFS做最短路计数的暴力，期望30分。

接着再来看T2，这很类似当年洛谷月赛的一道题Cyaron语啊，不过简单多了只需要执行For循环，我就用了栈的思想写了个模拟。可是后来发现了一个问题，如果循环的起点或终点引用前面的变量怎么判啊。后来想起了膜你抄里一句歌词“如果标算太难请坚定信念，不如回头再看一眼题面。”一看题目，没有这种情况，幸好幸好。读时间复杂度我手动写了个特别的读入优化，对于每个for循环判x和y的4种情况，调试了1.5h，过了两个样例，不出意外应该AC。

最后Day1出来期望得分230，觉得还算是比较满意的成绩了。

Day 1等待程序回收结果的时候拍的三中教学楼向下望的照片。还好考完出来感觉都顺利，要不然跳楼还真的挺方便的。（逃

考完回宾馆休息了一下然后去三坊七巷走了走，晚上去吃福州小吃。

撑着油纸伞，独自，彷徨在悠长悠长又寂寥的三坊七巷。

之后约了省冬认识的漳州一中的Pantw出来一起在西湖散步。Pantw还带上了他的一位同学一起出来。我们三个人中两个都是高三考完NOIP就退役，Pantw是高二准备考完冲省选。我们三个一起谈天说地聊人生聊OI。比较有意思的是西湖上有木栈道，我们每次进木栈道的时候都要遵循stack的LIFO原则，其中一次我们还记错弄成了queue的FIFO。

后来因为Day1下午和晚上走的比较累，晚上复习了一下网络流，之后就躺下去很快睡着了。

Day2的时候，T1刚读题目觉得可能是个比较难的计算几何，看图第一眼还以为是要算圆的相交面积或体积，读完题发现就是个求距离判断两个圆位置关系的大水题，我就很快花半小时码完，过了样例看后面的题去了。

T2一眼看以为是最小生成树，结果发现是个最小生成树的改版，权值还由深度决定，看了下数据范围正解似乎是网络流或者状压DP？然而拿网络流乱搞了半天也没能过第三个样例，状压DP式子死活想不出。最后拿SPFA的思想做了个BFS，显然SPFA是没法处理这种动态权值的，不过这种算法40分枚举起点做生成树的分数还是能保的。

T3一看似乎是个曾经听过的splay？可是我完全不会啊。又想了想这涉及到区间移动，会不会要写个4向链表呢，后来又想到这样遍历过去时间也过不去。又想了想会不会是个二维的线段树呢，可是最后想想还是不对。最后只好放弃打了个30分的模拟，然后继续乱搞T2。

最后乱搞T2的BFS，然而越改答案越离谱，中间还遇到了一个死循环因为Windows不好调降低了效率，然而并没有什么卵用，最后交的还是最早写的那份版本。

考完觉得Day2估分应该有170，加上昨天230总分大概能有400，这样应该能达到我考前立下的分数达到无论在哪个省都能拿一等奖的目标吧。

当时天上的云，隐隐地向我传达着不妙的消息。

离开福州三中前最后拍一下建筑。这也是我见到一些好看的建筑一直保持的习惯。

后来在QQ群和别人交流发现D2T1可能会爆long long，甚至要写高精，还存在double可能爆精度得问题。而考试出来我还在跟一个忘了sqrt函数的人说你直接拿2r的平方去判就好了，自己怎么就去用sqrt了呢。

回去的一路上循环听了数十遍膜你抄，觉得自己OI还有太多太多的东西没学。自己还想去学呢，怎么就只能回归文化课了呢。

哀OI之退役，叹没学的东西还很多。

已矣乎，寓形高中复几时，曷不收心赴高考。

之后OI回来的第一周上课便开始可疯狂补作业的日子。每当上课老师讲到无聊的内容时总是开始在脑海里回忆NOIP，尝试去hack自己的程序。每节下课都带着手机去厕所看看省计算机学会有没有把考生源程序发出来。

而一次的语文课我突然想到NOIP D2T1那题我把maxe只开到了maxn*2，我还记得我在写建图那部分代码的时候会想去改，却又觉得怕打断自己的思路，结果写完过了样例就忘了改。

后来源程序出来D2T1果然悲剧了，我测了洛谷、学军、清北学堂的数据分别是40、40、50。而我把存边数组大小加了3个0后，全都测到了100分，一下子少50-60分使我开始担忧。毕竟按照惯例，每年NOIP把正常人能打的暴力打满的分数段就是人最多的分数段，要是在这个分数段掉个60分岂不是连省一都悬了？

一周后成绩出来，340分，果然那题被卡40了。我看了下400分可以排福建省59名，340却只能排128名。不过集美中学平均分成了福建省第二名，第一名是福建省长乐第一中学。如果，我能在那个数组大小上加3个0，就能让学校成为福建省平均分第一了，可是没有如果啊。再过了一周省一名单出来，最高的省浙江省一等线360分，自己的分数低了20。还是感到自己很可惜没能完成曾经立下的目标。

最后尽管拿到了省一，但是没能在高中最后一次NOIP完成先前立下的目标，还是带着遗憾退役了。

现在，我没有抓住所有机会，只留下一张省一去自招的路来走。尽管这也是多数OIer最后的归宿。而与我一起学习的那些同学们，他们大多和我考了差不多的分数。他们大多数现在正在高一，还有很多的时间去冲刺接下来的省选，还有机会去考NOI。还有机会去AK NOIP，而这一切已经与我无缘。

这便是我高中两年多的OI生涯，它让我学到了自己没接触过的领域的许多知识，让我认识了许多OI的同伴，甚至教我了许多高考数学能用的更好的解题方法。使我的思维得到了锻炼，可是数列我还是不会证啊？

胜地不常，盛宴难再。集美中学的机房不再会有我的身影，我的OI生涯也就此终结。

是时候放下这一切，投入文化课的冲刺中了。