想写的太多,一时不知从哪写起。

<>Day -?

NOI前一个多星期,就回家了。一开始还跟着打打模拟赛,后面干脆连模拟赛也不打了。制定了刷题计划,可是积极性很差,一两天才能写一道题,一直在颓轻小说和漫画。整个人感觉浑浑噩噩,与其说是不紧张,倒不如说是特意忘记NOI的存在,刻意不去想不进队的结局。
其实模拟赛打得倒还行,大部分场都能排到前几名,还有不少次rk1。但是越接近NOI打得越差,后面习惯性爆炸,还经常失眠,于是跟妈妈爬了几天山,感觉舒服了一些。
NOI前几天,终于发现马上就要NOI了,自己还处于蒙蔽状态,感觉很绝望。晚上出去逛了一下,跟cjb聊了聊,吐了波苦水,纾解了一些压力。
就这样,NOI2019还是来了,在我的主场广州二中举办。一年的赛季,将以这里作为终点。

<>Day 0

Day0之前其实心态还好,背了背笔试就上场了。AK完笔试,顺便看了看试机题,第三题是交互,看来NOI居然加入交互了?第一题是优秀的拆分,是后缀数组题,之前写过,于是打算再写一遍。
考前很差的状态体现出来了,一个短短的后缀数组,被我写出了快10个bug。于是我花了1.5h调出了这道题,同学们早就试完机回去了,只剩我一个人在那里奋战。

记不清是怎么出来了,当时的感觉是完蛋了,只剩一个念头,赶快会机房写个大数据结构题。于是我选了lxl的大分块来写,写了1h写完了,然后开始跟常数奋战到晚上7点,怎么都卡不过去。妈妈来看了我一下,我让她回去了,心里只想着第二天的比赛没救了,想要放弃又不想放弃。后来听我妈说我当时脸色极度难看,让她非常担心。

晚上cjb给我打了一个电话,聊了很多,只记得他告诉我,试机赛爆炸无所谓,你明天的发挥不会取决于你今晚做了什么。大概聊了半小时,整个人稍微安定下来,于是点了个外卖,吃完洗澡睡了。

<>Day 1

晚上居然睡得还行。
早上再到机房坐了一会就上场了。开场时忘了按惯例写上比赛tips,强迫症还是选择在考试中间补上去了。

看了看T1,发现是个简单的斜率优化dp,于是先跳了。T2看起来是个挺奇怪的计数,T3是个挺奇怪的贪心,不过发现T2有50分裸暴力,T3有40分裸暴力,感觉还能接受,于是开始写题了。
飞快码完T1,为了求稳特意写了 O ( n l o g n ) O(nlogn) O(nlogn)的凸包三分,调过大样例大概9点。

在T2和T3中权衡了一会,感觉比起贪心,自己显然更擅长计数。于是开始想T2,照着50分暴力的笛卡尔树dp的思路想下去,感觉答案似乎是个分段多项式,是不是按APIO划艇的套路,用下降幂多项式做做就行了,于是我切了T2?感觉不太对劲,上了个洗手间,发现单次合并不是
O ( L 2 ) O(L^2)O(L2),而是 O ( L 3 ) O(L^3) O(L3)
的复杂度,总复杂度不知道飞到哪去了。回来也不知道怎么想的,花了几分钟时间写了个记忆化的测复杂度的程序,一测发现极限数据复杂度居然只有 4 ∗ 1 0 7
4*10^74∗107(考后才知道这个做法是 O ( n 3 ) O(n^3) O(n3)的),稍微冷静一会就开写了。

我先写了个50分暴力,然后开始rush正解,因为把多项式操作封装起来,写得其实还算快。写完发现无限RE,开始对着小样例爆调。因为不太习惯输出调试,所以结合着gdb使用。用起来体验比dev下的IDE集成环境体验差多了,结果花了一个多小时才调出来一个180行的程序。中间其实几次想放弃,但是之前模拟赛爆切全场唯一AC的数据结构题的经验给了我一点信心,不断告诉自己快调出来了,于是坚持了下来。

调出了T2,感觉其实已经稳了,接下来按预定写完T3的40分,就开始自觉对拍了。WC的经验告诉我,MLE是最大的敌人,于是特意测了一下时间和空间,确保没有犯下错误。
检查完文件名就考试结束了,下考后紧张到吃不下饭,跟zyy和zjc互相问了问分,就到了出分的时候。
看到分, 100 + 100 + 40 = 240 100+100+40=240 100+100+40=240
,心中只有庆幸的感觉。听说au线190分,于是稍微安心了一点。

<>Day 2

前一天晚上睡得很差,凌晨五点不到就醒了,困得不行但完全睡不着,于是早上泡了杯咖啡,还涂了点风油精。
考前一直在担心交互题,于是看了看JOI的一些经典树上二分交互题。
这次开场记得写上tips了,还是一样看完题,感觉一题都不会做,要完蛋?想起之前cjb说的,放平心态,先静静读一下题。

花了10min冷静下来,看完T1,发现88分的二维线段树很送,但是一时不会正解。想起来这道题似乎在claris博客上见过类似的,但是做法很神仙,感觉可能不简单,于是跳到后面的题去了。
T2按概率随机排列,让我想起CTS
D2T3,那道题花了2.5h拿到了20分,感觉不行。T3似乎是正常的图上交互,部分分很多,但是一时不想推,还是看回了T1。

想了10min,发现矩形的贡献是固定的,所以可以模拟Dijkstra,用线段树套treap,每次找出矩形中还没删除的点更新。这次写得很快,并不短的树套树,只花了30min就写完调完了。
心态稍微稳定下来,只要后面的题打好暴力,T1不写挂,自己就稳了?

感觉T2只有40分可做,于是觉得区分度在T3,开始玩交互。考前看的二分交互起了效果,A和B的部分分都很快用异或和的思路解决了。C和D似乎有点难,不过有了异或和的思想,也可以用删叶子的思路解决。这部分有68分,是很可观的分数。后面还有
n ≤ 1004 n \leq 1004n≤1004的部分分,感觉似乎能做?
上个厕所冷静了一会,回来写完了A和B,C和D遇到了一些麻烦,不过还是比较顺利地解决了,这时候还不到11点。
这时有点想收手,不过想起去年被队线卡的经历,告诉自己不能放松。于是对 n ≤ 1004 n\leq 1004 n≤1004
的部分分尝试了一会二分的思路,发现是假的。冷静了一会,想明白了问题在于可能一个点连出的边数目是偶数,这时候并不能二分。想起了之前模拟赛中出过的某道题,那道题通过一个关于组合数
m o d   3 mod\ 3mod 3
的性质,强行二分,所以我是不是可以构造出一个集合,使得里面和这个点连边的数目是奇数,然后就可以二分了?因为交互库是给定的,所以直接随机一半的点就行了。

写完这个做法,已经有了80分的可观分数。思考了一下,似乎满分算法在这个做法基础上修改一下就行了,然而很虚,于是把T2的40分码了。其实这时候还剩1h,不过稳妥起见,并没有写这个满分做法(感觉写的话是能写完的)。
最后害怕T1 MLE,特意测了一会空间就考试结束了。
这次主动放弃了吃饭,回到机房冷静一下。发现同校的貌似大多都考得不太好,然而T2听说是个sb题,所以也十分紧张。
看到分, 100 + 40 + 80 = 220 100+40+80=220 100+40+80=220
,紧张的心终于放了下来。跟场内其他选手交流了一下,惊讶的发现自己居然有前10的可能。
之后直接去THU换了保送约(这时候还没出分数线),然后四处闲逛。dcx D2考炸了,在线的边缘徘徊,尝试帮他看了一波代码,并不能复评。

晚上6点多终于公布了榜,我排到了rk7,是个之前根本不敢想的名次,yww和zjt也都稳进队了。dcx极其可惜,因为自己的失误被线卡了,为他感到十分难过,跟他一起训练了这么久,他绝对有集训队的实力,但是在最后的考试中失误了,非常可惜。

<>终点?

NOI2019结束了,进入了国家集训队,圆了一直以来的梦想。同行的伙伴们有的一同进队,继续走下去,有的却遗憾与集训队失之交臂。更多的人与高校签约,用一纸协议结束了自己的OI路程。

去年目睹这一切的时候,我还只是初中生,每天忙着orz各路dalao。每天跟在栋栋身边,目睹stdcall遗憾退役,听闻仓鼠因为后缀数组写挂而错失进队机会。当时我离队线5分,有遗憾,但因为没有直接利害关系,并没有太大的失落。

一年过去了,经历了NOIP的稳定发挥,北大集训的失意,WC的意外崩盘,八十中集训的新鲜,省选的意外之喜,THUPC与CTS的快乐,最终,以一枚NOI的金牌,为这一切画上了终止符。
感谢林老师,感谢父母,没有他们的辛勤付出,不可能取得这样的成绩。犹记得北大集训结束后最失落的日子,是你们开导了我,让我不要放弃,才能够终于品尝到成功的滋味。

同样感谢cjb,在赛前,赛中,赛后关照我,开解我。为了我,你操尽了心血,不顾舟车劳顿,特地在比赛后的第一时间过来询问我的成绩,不管怎么样,毕竟我达不到rk1,你也不用请吃饭啦!

更要感谢dcx,一年来,我们共同努力,打cf和atcoder到深夜,在QQ上聊题目,一起跟着博客刷题。没有你在的话,我自己不可能坚持做下这些,提升水平。这一年,因为有你的陪伴,是我训练最开心的日子。这次你虽然遗憾没有进入集训队,但是接下来你无论做出怎么样的选择,我都会理解并支持你。当然,更希望你能留下来,跟我一起再努力一年,争取进入国家集训队,我相信下一次,运气一定会眷顾勤奋的你。毕竟,我不希望接下来的路独行。

感谢所有帮助过我,与我同行过的OIer。季节变幻,同行的OIer也来来去去,很多人或许今后再无交集,但是以mayaohua2003这个ID的身份,我与你们结下了不浅的羁绊,未来的我大概不会忘掉你们的名字,以及当年一起走过的这段路,一起结下的友谊。希望你们在各自的道路上越走越好。

所以,这是终点吗?可能是,也可能不是。既然走到了这里,那么接下来的几个月,我也会以广州二中学生的身份,尝试挑战那些曾经高不可攀的目标,或许能走得更远,也许很快就停下。但是,既然有这个机会,那么,就试试看吧。

技术
友情链接
码工具
Toolsou
API参考文档
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信