GDOI2021退役记

要结束了。 尝试以平常的心态写下这篇游记吧。 ## Day -1 下午出发。 先吐槽一下司机，开一会就要鸣一下喇叭，开一会就要鸣一下喇叭，吵死了，但还是睡着了一会。 坐了两个小时才到深圳，感觉确实比ss周围繁华许多，道路也是真的穿梭的很厉害，但是感觉很多绿化都有点强行，有些路上甚至看不到天空。。 终于来到耀华实验中学。看着还挺大的，建筑风格和ss不在一个世纪。 领了狗牌看到是迷你公寓，以为是酒店破烂版。 去到发现nmgb是宿舍破烂版。下床矮的离谱，都是小学生宿舍，有点不爽。（好像只有很少一部分房间是这样的，然而中奖了） 去饭堂，发现没有能吃的，甚至还有干蒸，我觉得是早餐剩下的。。 突然觉得ss伙食还是非常好的。 取到小卖部买点东西，那个大妈像是我欠她500w一样，看呆了。 回到宿舍就开始打模板，复习复习。。感觉没啥好复习的，exlucas，pollard-rho,exBSGS这种数论毒瘤就放弃了。 感觉很无聊于是开始写游记。这天就这么过去了。 ## Day 1 晚上睡得还可以。 早餐有砖头，还好我没吃到（wxc和cdr吃了）。 进考场还是熟悉的戴口罩，不能动键盘鼠标。 进场看完题之后觉得t1非常可做，其他还不知道，于是开打。 很快就发现了key observation：只能从两边取。 想了个$O(n)$的做法，然后想了想细节，开始打，很快就打完，调了一些小错误之后就过了大样例。 发现大样例有点弱，而且这时候才$9:15$，于是想着先打个拍，拍了立马错。 又调了调若干小错，这个时候大概已经$9:40$了。一拍，过了好几组之后就错了。看了看发现和答案只有一个取值的偏差，于是加了点判断。 这时候过拍了，并且很久都没有错。 我寻思应该不用加这个判断啊，心态有点崩，考虑我做法的正确性。 想了很久觉得好像不太对，于是把数据范围开成$n=10$（之前拍的$n=500000$），一下就拍出错了。 改了个更加正确的$O(n\log n)$做法，由于中途思路不清晰，浪费了较多时间。 改完稳过拍已经$11:00$了。 剩下两个小时。 先对$B$进行了很多思考，感觉是个组合数加不等式组，觉得有点麻烦但我会做，先过了。 然后想$C$，本来就不擅长图论的我稍加思考，决定打个最裸的暴力。 回去想$B$，设了$n+m-1$个元，递推找找规律。 发现确实有规律，$(i,j)$之和$(n,m),(i,m),(n,j)$有关。 然后就开$O((n+m)^2)$个点跑差分约束就可以了。 觉得有点稳。上个厕所回来AC。这时候$12$点整吧大概。 zhendelan不知道，这是他day1噩梦的开始。 回去开始写，觉得思路又不清晰了，差分约束不会打了，打了一堆调到$12:50$也还是没有一点要正确的迹象，再看一眼暴力，好像又没有什么更暴力的思路了。这个时候心态已经很爆炸了。 再去稍微检查了一下$A,C$，调到$12:57$还没过样例就放弃了。。 想到正解打不出来，真的有点绝望。 估分$100+0+16=116$。 大家暴力都打满了，暴力标准分都$190$。觉得进队无望了，很自闭。 和oql说了一下。他和cmb都安慰了一下我，感觉就明天不留遗憾吧。。 下午心态好了很多，颓了颓ATRI，去听了听dzd~~生财有道的~~演讲。 晚上本来想打AGC的，但大家也都没什么心情，也是我就继续颓ATRI了。 $10:20$左右就睡了，听说cdr和wxc他们打代码到$11:00$。 ## Day 2 早餐cdr又吃砖头，笑死我了。 进场看，t1竟然是个传统树论，t2是个状压计数？t3不知道什么玩意的图论，怎么又考图啊。。 但这个时候已经是退役选手的心态了，非常平静。 t1走路很久，中途想到倍增套倍增的愚蠢想法，还好没有写。 大概$9:20$才想到关键的建虚树。建完虚树$s\to lca$部分就轻易解决了。 但是$lca \to t$的做法我一直想不到。想到$9:40$才意识到二分再套倍增就可以了。 脑中过了一些细节，确认正确性之后，非常熟练的一下子就打完了。 样例比较强，hack掉了许多小错。大样例RE了，改了一个小错，然后还是RE。。疑惑了一会发现是忘开栈了。开了就过了。 这时候$10:20$左右。 t2想到一个很垃圾的状压做法，还想到一个能过更多分的搜索做法。 但觉得状压可能可以优化，于是先打了状压。一下就过了前两个小的样例。 更大连空间都开不下，就别说时间还多个$n$。 感性理解+盲猜一波有效状态很少。 改成map优化，$n=11$的大样例跑了十几$s$。 开了O2就跑到$2s$左右了。 而且完全看不出有啥优化空间。 去把搜索打了，$n=11$跑了$1.2s$,但是$n=12$跑的比状压还慢。 改成舞蹈链之后快了一点，更方面都比状压快了。 然后又改了个记忆化的dfs，写完才意识到适合状压记忆化一样的。 我观察到$n=12$时有效状态只有$1000w$，我想用哈希来优化一下，但是感觉不太行，空间常数和时间常数都太大了，于是丢了。 这个时候已经$12:10$了（因为打了太多个版本的代码）。 去看C，发现有个显然的$O(nmq)$做法。 打完还顺便把树的打了（这个其实情况有点多，我也不确定我有没有打对。。） 这时候$12:50$了，没什么好做的，检查了一波放弃了。 一看时间已经$12:53$了，突然意识到我的OI生涯只剩下7分钟了。 很多回忆突然就涌现出来了，想起之前和cdr看的游记，还经常调侃在考场倒数退役，在什么txt打下退役，感受自己OI生涯的最后几分钟啥的。 真的好快啊，我也到了这个时候了，该说道别了吗。。。 打开txt，把字号调到最大，写下了GoodBye OI的话语。 结束了。 # GoodBye OI 衷心感谢OI生涯中给予我许多帮助的同学老师们：包括但不限于cdr、oql、pht、cmb、ss、wjw、lkb、pzs、wlr、py、lby、jt、lgj、lhl、lfl。。。。。。。。。 也希望如果进队了的cdr，还有F4中的各个大佬EA、ustze、hs_black、AzusaCat、lhm、jiazhaopeng加油，NOI Au。 也希望学弟dby、czy、wxc、cjy、xcy、xzd、lsy等人加油吧。 放一些有纪念价值的东西：    本来是Master的，掉下来了，也没空打了。 还有一个很有意义的就是这个博客啦。 虽然其实模拟赛做的题更多，自闭的也更多，很多写的东西也没有全放在博客上（因为习惯在本地写东西了）。 最遗憾的东西就是没进队吧，还有就是至今还是蓝钩，连个金钩都混不到啊。。还有好多想学的东西没学，多项式理论依然很菜，二次离线依旧不会，图论依旧很菜，SAM只会乱搞，计算几何和图论菜的离谱。 最开心是和cdr一起随机跳题，还有爆切AGC全场只有$5$个人做出来的E。还有模拟赛不被zzz和EA踩。(还有osu！、听歌和看番)。 叨叨了很多没啥用的东西的样子。。不知道说啥了。 文化课加油，有空还是会打打CF和Atcoder的。 再见，OI。 さようなら，OI。 2021.4.11。 upd:100+0+16+100+60+45=321一分没挂，但要再多一百分才能进队，还是退役啦。