蒟蒻的NOI 2020退役记
Day -1
在中午太阳晒得最狠的时候到了学校。宿舍爬楼累死人，也不知道为啥学校楼要建那么高。幸好宿舍里的空调给力，好评。
宿舍的环境还行。个人觉得比当年WC2018的要好。
信号出奇地差，必须在直接靠窗的地方才有4G，不然连2G也别想收到，听宿管和小卖部阿姨说当初就是设计成这个样子的。差评。
插座很多好评。
但是还是没有桌子，无论用什么姿势看电脑都贼难受。同寝室的jtl带了一个床上架的桌子，看了直呼内行。床板贼硬，差评。
伙食还可以，豆浆我觉得挺好喝的，就是湖南菜多多少少带点辣个人不是很能接受，而且菜很细碎的样子。
睡前随随便便背了点笔试题。
Day 0
早上迷迷糊糊地去参加了开幕式。听到dzd说有剩饭扣1分大惊。其他就没啥印象了=_=。
结束后拱火mr押题，mr说看到才艺表演一个跳舞的转来转去暗示会考平衡树，一本正经胡说八道.jpg。
感觉周围大佬都贼多，互相之间也都认识，我一个蒟蒻在当中不知所措。自己看来对于在竞赛圈内的信息闭塞的可以。
中午又背了一会笔试题，然后下午就去试机了。笔试没有想象中的难，但是确实是有超纲的，纠结了很久。幸好最后还是满分飘过了。唯一值得吐槽的或许是CCF十年不变的远古测评系统。
随后在试机场上敲了一波LCT和FFT。看到jtl在写MTT有想敲三模数的冲动但是最后的合并调了好一会才勉强调出来，于是就很慌。
晚上寝室里大家都在欢快地打板子。对面两个人都在打带花树，然后惊奇地发现带花树的代码似乎也没有想象中那么长。三个人讨论了一下觉得似乎有概率考分块的样子，但是笑一笑也就过去了。我自己把各种字符串的算法全部过了一遍。
Day 1
看到T1愣了好一会，愣是没有第一时间看出DP。不知道为什么当时满脑子都是Tarjan和缩点然后沿着这个方向陷入了死胡同。于是先敲了一个DFS，觉得自己要完蛋。
看了T2又愣了一会，先敲了个暴力，然后觉得比较小的情况可以动态维护链并+容斥解决。先放着。
看到T3深切地感受到这或许是个数据结构毒瘤？先敲了一个二维树状数组的暴力。当时脑子大概是坏掉了不是枚举矩形直接算而是枚举点算贡献。总之暴力复杂度似乎非常差。然后认真思考了一下部分分，发现可以莫队。于是基于二维树状数组写了一个
的算法。然后觉得
的二维数点不妥，改成了
的可持久化线段树，于是暴力和莫队的复杂度都少了一个
。再一看发现莫队我可以用树状数组干嘛要二维数点，于是莫队的常数又降下来一点。瞄了一眼后面觉得应该可以用
的四维莫队，可惜当初没认真学高维莫队不知道块大小咋算了，于是作罢。最后敲了一个莫队和暴力的对拍放着。
回到T2开始敲树剖和容斥，写了一个的算法。和暴力结合在一起觉得至少能拿
分，常数小一点也可以冲冲
样子。
然后回到T1，突然发现这不就一个裸的DP吗，直骂自己前面傻逼。于是花5分钟敲完朴素DP，然后再花10分钟敲完环的部分分。
然后发现边权至多为，意识到正解显然是用max-plus
algebra下的矩阵快速幂进行优化，于是开始敲。此时离考试结束还有60分钟，心中贼慌。等到敲完离考试结束还有30分钟，心态爆炸，然后死活调不出来。只能把这个正解例程写在程序里作为最后之选。离交卷还有5分钟的时候不改了。检查其他两题的程序无误后就开始坐着怀疑自己前三个小时脑子到底在想什么……
出考场觉得自己已经成为了时代的眼泪（笑）。
下午三点去查分。听jtl说这次CCF准时出分没有咕简直是奇迹。结果就是。和预想的完全一致。这个时候就很后悔。如果当初早点看出矩阵快速幂把T1的正解调出来就好了。这个分觉得铁牌已经在向我招手。
晚上讲题。T1的确是快速幂正解。T2的正解是线段树合并维护树形DP这个之前也在寝室里有了大概的想法，但是一看这个DP的状态设计果然神仙。出题人怒斥了我们打分树剖暴力的，说是什么数据结构学傻了……然后说写个虚树不就
了吗。我下面听着就很无语：我也想打虚树，但是我不会啊……
T3的出题人原来就是各种OJ上人们一直吐槽的lxl。这个题目的内部名称似乎叫“第十三分块”？正解似乎是先建一个树套树然后再分治再分块……讲到一半就lost了，内心大骂出题人毒瘤。
回寝室后所有人都是颓废的状态，gyc在打Splay的板子。剩下我们两个人开始摸鱼。
Day 2
T1一看给人一种网络流的既视感，然后发现图建不出来。退而求其次试图写出线性规划进行代数化建图，发现线性规划必须使用Big M的办法才能建出来，而且直观一看integrity gap大的离谱是不可能建图的。因为是求可行解也不知道目标函数咋写，所以也不能从对偶下手，只能作罢。敲了一个非常粗暴的DFS暴力枚举每道菜用哪两个原材料分别用多少，发现这个DFS在最坏情况下跑得巨慢无比——难不成我暴力骗分都不成？
这个时候有了一个乱搞的intuition，就是枚举原料的排列然后按照排列来确定所用的原料。然后发现过不了样例，于是作罢。
之后稍微改进了一点暴力，只枚举每道菜用哪两个原材料，最后时候用多少最后用网络流来判。这下终于拿到了分的暴力。顺便基于这个敲了一个随机化，但是似乎表现也不佳的样子。
T2题面长度属实劝退。读完题面之后觉得似乎不是很可做。看了样例之后有了一点暴力的想法，写了一个复杂度为的算法。简单来说就是把输入的树补成最大树高然后枚举能否扩张成最大树高下的所有可能的二叉树形态。觉得除了
分纯暴力还可以拿
的分？之后就不会了。
T3一看给我整懵了。可真就暴力不会写呗。直觉上似乎可以写Dijkstra然后在转移的时候排除掉当前路径下的割边。但是很快意识到Dijkstra的本质是DP而这个转移方案是有后效性的。事实上也是如此，样例都没有过。然后试验性地写了一个不可行的判定方法：求出最短路，如果把最短路去掉之后全图不连通，则不可行——也不知道这样对不对。
5个小时就在三个题目的来回懵逼当中度过。
这次CCF出分直接咕了将近两个小时。我们很明智地从一开始就待在寝室里，那些下去等分的就苦逼了。分数出来是、也差不多是我预想的这个水平，T2树高为
的点我还是超时了，大概还是没有判同构去重的原因？
下午去听讲题。T1正解的思路源于的思考，其他的情况都是向
情况的规约，感觉是非常巧妙的。T2的最优算法居然是线性的？有点听蒙了。听到T3讲解的时候才意识到T3当中的图叫做弦图，而正解源于对于弦图性质的思考，最后用过两次类Dijkstra来解决，感觉是非常非常神奇，不明觉厉，自愧不如。
讲的时候就出榜了，一看果然Cu，心情复杂，但是一开始也没有期望，所以也没有太沮丧。感觉心态真正崩盘的大概是jtl，人家Cu第一……差一分就Ag了。但是看榜还是有分以上的，觉得这些人真的很厉害。我或许不比他们笨，但是他们确实历练的比我这种多多了。我这种常年边缘划水的OIer果然不能和这些人比。
Day 3
看着手中的铜牌，意识到自己划水的OI之路至少到此为止暂时地画上了句号，颇有些不真实感。
我一直在想，如果D1T1的正解我调出来了，我就是Ag了，会不会好一点呢？但是这终究也只是一个幻想而已罢了。一是比赛不能重来，二是我似乎也不知道缓存矩阵乘方的套路所以真写快速幂有可能复杂度还是会炸的样子。
一如既往，自己复习的算法完美地和考试算法错开了。没有LCT，没有FFT，没有字符串。我深切意识到OI果然还是靠平时积累的，这种比赛临时抱佛脚很大概率是不靠谱的。
还是要谢谢NOI最后给了我一个意识到自己有多菜的机会。还有那么多我没有学的啊~
大概在没有竞赛压力之后我还是会对这些算法认真地研究一番的吧。觉得自己的心态是一个很奇妙的东西。在被父母逼着学竞赛的时候总觉得这些算法很烦，但是意识到自己远离竞赛之后，反而又觉得它们有趣起来了。
网上看过很多这样的游记，一般到最后作者不是Au就是进队了，这种好事终究不会发生在我身上。
唉。这就退役了。
写于Day 3从长沙回上海的火车上。自己的思路一如既往地混乱。