OI回(liu)忆(shui)录(zhang)

作者: 99hgz 分类: ,长文 发布时间: 2010-12-31 15:49

Q&A

Q1:你是哪里来的菜鸡?
A1:高一蒟蒻,坐标浙江,现在YYHS整日摸鱼
Q2:你明明比我强还说自己是菜鸡,你好fake。
A2:人外有人,天外有天
Q3:学OI难么
A3:越到后面越难啦,现在看来一个好的学习&交流环境是能让你事半功倍的。强省+强校真的是可以为所欲为的?!
Q4:为什么现在就发回忆录?你才高一啊。
A4:明年可以再写,把游记补一补罢了。
Q5:博客还更么?
A5:会的,虽然本来频率就不高。
Q6:你欠的女装什么时候还啊
A6:咳咳(捂脸光速逃

前言

作为一个学了7年的OIER,最后马上就要滚去学文化课了,趁此空闲的机会,还是来写点什么。开码之前,先感谢下文中出现过的所有人一波。

初入此坑

跟很多高一才学习OI的大佬比起来,我开始学习OI还真的是早啊,小学四年级就被拉入了编程兴趣班。突然想起来我接触电脑应该也是很早很早的事吧,在QQ农场,抢车位什么还流行的时候就接触了HTML和Photoshop这些东西,查了下百度的话应该是09年到10年,也就是是小学两三年级。所以应该是当时父母也有这个想法然后正好学校也有这么个条件,然后搞了个什么选拔做了几道数学题就这么入坑了吧。

一开始肯定先学Pascal的基本语法,总感觉学了好久好久。当时是每周二四的晚自修(小学的晚自修是真tm的苦逼)+周三的活动课的时间来学习编程的吧,然后暑假还有集训(当时还有暑假),这么多时间好像也没干什么,主要去了两次余姚市的小学组信息学竞赛还有宁波市的比赛。

容我去查查百度。

Emm怎么说呢,还行吧。也许这是支持我继续走下去的原因吧。可以发现第二份名单上的人,也是都汇聚到了余姚中学,而更下面的人,应该多半是没有继续走这条路了吧。

然后一个比较受打击的事情还是宁波市的那场比赛,只拿了个二等奖,没有直接升初中部的机会,还是非常气的,再者就是对信息学竞赛的认识也比较少,拿个宁波市的一等奖就挺好了嘛hhh(Naive)。

我想看看当年是谁吊打我的,结果 %%%LZW%%%

当时确实是什么都不会,完全没有数据结构的什么的概念(其实初中也是,但我相信大佬们应该都学会了),然后比赛的话就是自己随意发明创造,被吊打也是很正常嘛。

在扯一扯呢,小学的时候比较崇拜的就是徐泽涛了,很神(现在也是神得不行啊),可以随意在oj里虐题,碾压我这种渣渣。当时大家称其为老衲,写了一个游戏是贪吃蛇,我印象深刻,真的很6。

初中

小学其实也没什么好说的了,然后在刻苦学习文化课的情况下,还是顺利升到了初中部,那么肯定也是继续学习编程,但是这个不同学校来的人带来了不一样的资源,就可以开始在机房搞事了。

相信有很多的OIER也是这个时候入坑的吧,恭喜你们享受了一段悠闲的时光#斜眼

初一的时候认识了ax_pokl这位大佬,他用pascal编写了display单元库,然后还有一些用pascal写游戏的资料。自己也写了不少东西,有一个用socket单元库写的聊天室(后来还支持传输文件,具体速度反正能用),还有为了实时获取程序的输出研究了下windows的管道。

初二的时候呢,就开始在机房里打隔膜了,初三亦是如此,周四晚自修也是车开得飞起,集训的时候每天必开cs,所以当时的做题量真是少的可怜。

当时的目标也就是拿一个noip普及组一等奖。

第一年noip2014,初赛试题出锅(GGF预定),因此离分数线低几分,用了个推荐名额,又成功跪掉复赛,掉入二等。讲道理当时回到家里,突然就想起来T1怎么错了,也是比较难过的事情QAQ。

第二年noip2015,最后一题推销员,贪心乱搞洛谷数据20分,官方数据100,也是运气非常好了。成功拿到一等,为之后的颓废做铺垫,其实最后也没什么用。

第三年noip2016,可以说是被碾压的很惨了。本来想去提高组摸鱼,但是后来搞了一次模拟赛,死的很惨,记得d2t1是一道最小生成树?但当时是完全没有概念,根本不会写。考完后也是心态炸裂,第一次感到自己真的好菜啊,然后继续在普及组划水,也没有一个很好的成绩,但是上文中提到了那位大佬AK全场,真的是太劲了。

这一年的noip搞完差不多就是面临升学了,然后又几经周折才到了余姚中学,继续享受被碾压的快感。

高中

由这个成绩可以看出整个初中确实啥都没干,一进来就被各位普及组ak大佬,提高组大佬碾压。确实什么线段树,树状数组,并查集,SPFA这些比较基本的算法和数据结构都没有听说过,就只能在中游混混了,心理落差比较大。然后只是这样的成绩的话还是拿不到一等奖的,十分的慌张。再加上班主任的压迫,没法拿出更多的时间花在编程上,处于GG的边缘。更气的事情是当时班主任愿意选几个人多给几节晚自修搞OI,这个还没有能轮到,可能真的是太菜了吧,也真的考虑过不搞竞赛了(还好没有),毕竟文化课也是辣鸡的不行。

一开始就用的是算法导论作为教材,真心感觉很难,偏向理论。当时觉得比较强的大佬有很多(其实都比我强),但是我不习惯与别人交流,由于比较菜的缘故,也没有人来和我交流,这个还真的是比较难办的事情,其实直到现在也是如此,不愿意去麻烦别人,也许是怕大佬觉得这个问题十分的水,只好自己慢慢寻找答案,往往要花更多的时间。

然后的一些比较重要的事情就是pascal转c++,再后面就是刷bzoj了吧。刷bzoj这件事情相信是每一个浙江的提高组选手都应该做过的事情吧。翻了翻记录,最开始ac的是一道三分的题目,然后代码还是抄的(逃。再下面是斜率优化和Splay(其实斜率优化很后面才会,Splay到现在也不会)。然后就是有关图论的什么假期的宿舍,狼抓兔子。现在看到这个题目名称还是像昨天刚做过一样,很熟悉的感觉。这里说几句大实话,希望何开看到不要说我太Naive。就是说,其实吧,在来余姚中学之前就认识何开了,我竟然一直觉得这人应该比较菜的吧,然后就被碾压了。而且何开还会一些我完全不会的东西,什么树链剖分,斜率优化,令人佩服,本萌新确实是策策发抖。所以也是非常的不服,就开始跟在大佬后面刷题,也算是比较早开始刷bzoj的了吧,刷的量应该也算还行。当然再这个领域的话我也是很佩服夏逸帆和冯志远,看文章的各位应该都知道,就不再多说了。开始刷bzoj之后就是暑假集训了,感觉这两件事情加起来还是很有帮助的,成功把不会的知识补了起来。

再来说说机房吧。上课的机房CoreE系列CPU+2G内存+XP,可以说是打CS的好地方。有时还能用VNC连到隔壁机房在上课的时候划水。坐我旁边的一般是陆浩旗大佬。然后隔壁就是省选机房,Corei3+4G,考虑到长远的需求,加钱到了8G+SSD的配置,配合win10确实爽的飞起,但是地理位置就比较一般。右侧是成佳悦同学,然后是大佬三连。左侧是公用的服务器,用elementaryos,搭建了一些不可告人的东西。说实话机房的环境确实不怎么样,也还行,就是脏乱了一点吧。

下面进入较为连续的比赛时期了,首先是最重要的NOIP,考挂了就直接退役了。

NOIP2017衢州二中

第一次参加提高组,非常慌张。Day1,第一题,卧槽居然是数论题,要GG了,先冷静打个表,居然有规律,上对拍,后来才知道这样似乎是正确的做题方式(大雾)。第二题,模拟模拟,感觉分分钟写挂,手工写了个栈,大概对着大样例调了1h,然后就丢到一边了。看t3,感觉很不可做,先码一个时间复杂度和最长路长度有关的dp,能拿几分是几分,但是在考场上脑子短路,判-1的情况写的是错的,好在最后没有被卡掉,拿了标准分。Day2的话打的比较顺利(Flag),t1无脑dfs,然后就没有检查了,成功少写了一个0,不过好在人品爆发没有被官方数据卡掉。t2状压一波,也顺利拿到分,此时大概还有一个半小时写t3,非常稳的感觉(并不)。开始读t3,就感觉是个数据结构题,先开始想写一个平衡树(并不会),然后考虑了一个线段树的做法,又怕被老爷机卡常数就改成树状数组,应该可以拿一些分(最后一个临时变量开成了int,成功炸掉两个点),应该还剩下20min,然后想到了正解,把线段树动态开点,然后维护一些信息就可以了,然后就手抖地码了一会,最后还是放弃了,事后的话发现还要思考30min码30min调1h才行,思路比较绕。这场打的还行吧,也是努力了好久了,还是等成绩的时候比较忐忑,我怎么就手残少写了一个0呢。

 

安徽集训 安徽师大附中

题目我是不记得了,玩的倒是挺开心的(大雾

 

THUWC雅礼洋湖实验中学

这场是妥妥被虐。

Hgz打开了day1.pdf

Hgz觉得T1可以贪心

Hgz开始写代码了

Hgz交上了第一发,取得了7分的好成绩

Hgz觉得这个贪心有点假,有很多特殊情况

Hgz决定手工分类讨论

Hgz交了22发,还是保持7分的好成绩

Hgz决定先上个厕所

Hgz开始写后面两题的暴力

Hgz滚粗了

Day2的话也没有什么好说的,t1被卡内存,t2t3暴力,翻盘失败,没有进面试。当时的政策是说进了面试的话就有直接进入夏令营的资格,所以还是蛮重要的。

WC2018雅礼洋湖实验中学

CCF组织的冬令营就跟在THUWC后面,先在第一课堂划了几天的水,本以为自己总能听懂些什么的吧,事实上emmm,所以明年应该去第二课堂听课?然后的话图书馆变成网吧也是比较资瓷的,因为电脑被何开抢去了,所以这几天学习了下毒瘤的后缀自动机。比较辣鸡的地方就是宿舍网络比较差,不过床边有插头的话晚上还是可以看片的,然后就刷完了黑镜还有几部电影。食堂也是比较好的了,就是人比较多。

WC的比赛只有一场,t1想了一会发现可以点分,因为部分分比较多,看了大概有一个半小时吧,然后开始无脑写点分。求树的直径?点分!一树两链?点分套线段树!两树一链?分成四段点分!然后成功没写完+被卡常。T2写暴力的话还要判欧拉回路(我不会),果断放弃。T3想了10分钟就可以拿到45分的好成绩,十分良心。

最后T2出锅,用两套数据测取最高分,反正我也没写。混了一个铜牌滚粗,何开依靠T2翻盘,拿下银牌第一(误),实在是太劲了。

ZJOI2018 Day1衢州二中

讲课什么的肯定是要翘掉的,明知准备了也用不上的,还是偷偷做了会题。也是这个时候darkbzoj开放注册,可以说非常兹磁了。

T1明显要推推式子,并不擅长,貌似30分还是挺好拿的,先打了走人。

T2的话讲道理就应该是数据结构题了,想了将近两小时后发现应该就是贪心了,在修改一个点的时候会更改整条它到根的路径,感觉很像可以用LCT维护一下,然后就AC了?感觉很假,先写了个暴力跑了一下大样例,并没有过。其实这题我题目看错了,但结论好像是对的,然后就成功GG,爆0了。

T3完全没有思路,构造的题向来是没怎么做过,很不可做。先写个暴力,但并不能跑出来。也成功爆0了。

考出来心态爆炸,这么点怎么见人啊,整场比赛就前30分钟得分了,后面不如睡觉QAQ。凉凉。

ZJOI2018 Day2余姚中学

Day2翻盘?不存在的。

看到T3的一瞬间,我就知道这套题有多毒了,这也能做???

T1有关树的同构,慌的不行,完全不会判同构,照题面中给的方法是阶乘的,就是打表也不一定能在5小时内跑出答案。想了一个小时最后枚举树和排列,用并查集判重打的表。至于n=20的点,这能做???

T2跟Bellman–Ford有关,看到题目的瞬间也是慌张度++,完全没用过的算法。往数据结构的方向去想,貌似是要维护一堆斜率±1的线段,求在一段区间内的交点个数。分块?扫描线?发现并不会维护,反手一个20分暴力。

T3只能说神仙题了,n=3直接输出3好像有点道理?n=4莫非能推一推?可是我连样例都不会算,微积分什么的不存在的,果然是我太菜了。又写了个随机撒点滚粗了(万一运气好/数据水)。

ZJOI的话感觉暴力写满就到前48了,稍微比别人多拿一组点就30-了,还是可以考虑一下的。

CTSC2018  北京第八十中

继续翘掉讲课。

D1T1一个比较显然的dp,暴力n^3,发现可以从两侧dp,用ntt合并,无奈忘记ntt怎么写了(听说ntt也会被卡常?)。

D1T2写了个n^2的dfs暴力,拿了40,需要LCA转RMQ才能拿到剩下的5分,坑逼出题人!本来还想写部份分的,来不及了QAQ

D1T3完全没有思路,DFS+Hash走人。出考场发现还自己hash写错了,还好没挂。

听说这里的noilinux还没有计算器???一直用python当计算器的选手表示完全没有发现。

继续颓颓颓

D2T1不穿衣服的主席树题,我居然想了一个多小时。

D2T2这题暴力怎么写???

D2T3整场比赛3个小时在写这道题。第一次在比赛里刚提答题。首先冷静地读完题面(内心OS:这么长题面看着也不大可做),先想一个通解拿点分,估计也只有模拟退火乱搞了,这数据范围这么大也能退火啊(事实证明可以)。后来还是老老实实一个点一个点刚下来的,拿了60,中间还跟c++的字符串搞了一会。其实此题考验选手会不会用那个simulator。

剩下时间就是颓废啦。

APIO2018 北京第八十中

上场困得不行,看了看T1,感觉很毒瘤,一定是道数据结构题,差点就想趴着睡觉了。随机想了一些方法,大约用了1个半小时搞出了一个非常暴力的两个lg的做法,此时瞟到我左侧的小哥已经把三道题全交了几发了,TM瞬间就惊了,赶紧开始码T1。前两发连续暴零,只好写对拍,改掉了一些神奇的错误后大概还剩一个半小时,一发交上去,直接TLE了。当时感觉T1是道签到题,全场都会,这不行啊,肯定要先卡卡常,主要把在set中删除元素的find去掉改成直接删指针,快了大概1s,想着这老爷机都能跑过吧,一发依旧TLE,此时还剩一个小时,在继续卡常与写下面的暴力之间挣扎。最后决定先优化下插入的部分,多拿了10分,然后写了T2的暴力。最后卡了Ag线,Au变Ag,非常气。

出场听说T3是大思博题,可惜我看都没看一眼。

 

北京这几天还是非常休闲的,就是钱包有点撑不住。去地坛,去天安门,去玩密室都还行吧,晚上继续一波看片划水洗澡睡觉简直是咸鱼生活。比较不爽的是路上花了不少时间,还有八十中的饭菜也是有点抽象,宾馆大(xiao)床房也是被各路OIER喷的飞起(我闻到了给给的气息)。

 

THUSC

留坑

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注