NOI2020 前最后的日子

2020 年 8 月 10 日，省队集训 Day3，开此博客。

每个 OIer 都从这名叫“菜”的泥潭里出生，尽力摆脱这里，飞向更高更远的天空。然而真正能展翅高飞的毕竟只是少数人，大多数则永远无法冲破束缚，最终被埋没在泥潭中。

显然我没能摆脱这片绝望的泥潭，时间却已耗尽。尽管人生还很长，但 OI 生涯的主线已经到了终点。

就用这片博客简单记录一下最后这几天吧。长短视心情，当然文笔还是一如既往的差。（开始担心回归文化课后的语文学习了……）

8.10

上午 ckw 模拟赛，自称“这是你们这几天唯一有可能 AK 的比赛”。T1、T3 是数学题，T2 是数据结构题。我做掉 T1、T3 后在 hyw 的提示下在最后一刻过掉了 T2 的大样例。

中午回来看评测，果然 AK 是不可能的，T2 喜提 20 分。据说数据造错了，写对只能拿 60，可是这丝毫不影响我只配挂题的事实。hyw 1h 连写带调 AC，我在提示下 1.5h 过大样例还挂，简直天差地别。

下午听 wqy 讲课，遇到各种西伯利亚题（指恶心的输出方案、卡精度、无理由随机等迷惑操作），甚至有道交互题做法竟是“随机若干个排列进行询问，然后对这些询问的结果退火”，大开眼界。当然也不乏令人眼前一亮的神仙题。swkdz&lyhdz 全程秒题，神仙就是不一样。

一群人在一起，听讲课、讨论、口胡，真的好有意思啊。可惜只有最后这几个下午了。

晚上回宿舍后尝试调挂了的 T2，发现给点分治树的每一层都开了一棵主席树，修改时只修改某一位置往上的层，但忘记了把其余层的根也从上一个历史版本复制过来。冥思苦想了一小时自己为什么想不到这件事情，但显然无济于事。睡觉时脑海中只有四个字：无药可救。

8.11

上午 cwbc 模拟赛，T1 大数据结构，T2 图论，T3 是很简单的思维题。这是我最自闭的一场，也是前 6 天唯一一次一道题都做不出的比赛。由于昨天的心态崩溃，我看了 T1 后默念一句“数据结构与我无缘”果断放弃。但感觉后两题更加不可做，不到 1h 就弃赛心有不甘，于是又来想了一会 T1，写了一半发现假了，又刚了 2h T3，写完发现假了，暴力也没啥好打，最终零分收场。hyw 想出了 T1 的线段树合并神仙做法，并用 1.5h 写出 4kb 代码过了样例，lyhdz 写出了三道题的正解。cwbc 说 T3 是最简单的题，可我做了半场，依然毫无思路。

中午看评测，hyw T1 写挂了一行代码爆零，可总比不交题的我强无数倍。lyhdz 三题都写挂了有点惨，但三题正解还是绝无仅有，唐爷爷 35+85+100。我只有围观神仙打架，质疑着自己这水平到底是怎么进的省队。

下午 cwbc 讲网络流，也是听得最自闭的一天，大概我不仅智商不够，网络流方面的套路也没有掌握好。等回去再好好学习一下……哦不，没有时间了。

晚上省队统一做核酸检测，解锁新体验。大家一致推选队长 swk 先来，然后医院真的让 swk 先来了233333 迫害队长真好玩。并没有听说的那么难受，就像医生让病人张大口并压住舌头一样，最多在一两秒钟的时间里有呕吐的感觉。

回宿舍后尝试写上午的 T1，先自己 yy 了线段树合并做法，写完且过了样例后已是午夜，一测喜提 10 分，顿时意识到自己做法又双叒叕从头假到尾。两天做 5 道题一共想了 4 次假做法，国赛现场想一次假做法就有大量的宝贵时间被耽误，这么高的概率想假做法意味着必定凉透！反省了一下，也许是想出做法时的迫不及待导致的？水平问题就认了，心态问题还要努力克服一下啊……

8.7 前往省队集训；8.9 最后一场 AGC；8.11 核酸检测；8.12 最后一场 CF；8.14 最后一场 OI 模拟赛；8.15 APIO；8.16 长沙报到……

8.12

上午 cz 模拟赛。（cz 学长赛高！）依然是三道没啥思维难度的套路题，T1 是网络流，后两题数据结构。T3 是之前我给 cz 验过的题，T1 猜了个贪心的结论省掉了网络流，900B 代码 A 掉了。T3 码量不大，但我写 25min 调 25min 依然不尽人意。剩下的时间猛刚 T2

中午看评测，T3 被卡常了，100+0+90。我的做法和正解复杂度相同但常数稍劣，加上自己写的时候也不注意，随手就能加的优化却懒得加。几乎每场比赛每道题都有人 A，而我因为数据结构水平太低又被 T2 这道数据结构题挡住了。

下午 cz 的讲课内容是喜闻乐见的数据结构！很长时间以来我都不太喜欢数据结构（特别是写重工业题），也以为数据结构题都是无聊套路题，最近才意识到其实里面有着很深的学问，可惜我也没有时间多研究了。谁都清楚数据结构在 OI 中的重要性，如果 NOI 时被数据结构题制裁了就只能怪自己没认真学习了。
cz: “所有数据结构都只有一行代码”

晚上根据 hyw 的提示继续写昨天的 T1，问了好多这题的智障问题……

22:35，还在调试的我关掉手中的题，转向一件更加重要的事——NOI 前最后一场 CF。
Codeforces Round #664 (Div.1)，出题人是高爸等几个中国人。曾经徘徊在 2300 上下的我绝未料到会在 OI 生涯的最后时刻沦落到这个地步。现在的我屈居紫名与橙名的交界处，曾经的红名梦早已在那场 -205 的噩梦中化为泡影，而有关 CF 的另一个梦想——Div.1 top100，对我的水平来说也并不现实。在最后一场比赛里，我仅仅想顺其自然地放手打一把，能打怎样是怎样——当然还是要守住橙名的底线，带着紫名去打 NOI 怎么都说不过去。

A 题没啥思维含量，15min wa 一发过了，看起来这场的风格相当套路。B 题题意读了好一会，意识到这是一道没有思维难度的题，但是码量稍大，稍有不慎就会调上四五十分钟。挑战自我的时刻终于到了！我一边敲代码，一边提示自己千万要冷静，认真思考每个细节。最后很快调了出来，码长 1.5kb，38min 的时候 pp 了，从看题到做完一共 23min。
这时我打开排行榜，场上一共只有约 60 人过了 B，我排到 rk58！这是我历史上在 Div.1 比赛的任何时刻达到过的最高名次。一刹那，我心中闪过一道光——或许，我今天，能够实现 top100 的梦想？
打开 C 题，我束手无策：计算几何？数据结构？这到底是什么？大概想过不少荒唐的思路，终于在 1h19min 的时候想到了做法，1h46min pp。这时虽然已经有 120 人过掉了 C，但是由于 B 题还有一定的速度优势，我排在 rk79，到比赛结束时，约有 200 人过了 C，pretest 成绩 rk88。
我仿佛触及到了遥不可及的梦想——近在咫尺，只要不 FST！但谁知道我的代码里会不会有什么鬼畜的漏洞……我一边等 system test，一边继续写昨天的 T1。AB 都已经 Accepted，C 很快就要测到，万事俱备，只欠东风……
“Wrong answer on test 24”. 因为写错了两个变量，我最终与 top100 失之交臂。不知为何我在如此关键的位置写错，18 组 pretest 竟没有卡掉。也不能怪 pretest 水，我真的就是菜了点，就只是，菜了点。（或者运气差了点？）

我查出了 C 的错，并终于过掉了昨天（前天？）的 T1，此时已是凌晨两点。最后上 CF 看结果，rk170，右上角竟还有个醒目的“You have+118! Wow!” 就这样，我的 rating 最终定格在了 2218，比我校榜内最高 hyw (2221) 低 3，比自己的历史最高 (2393) 低 175。

我躺在床上，想起这个 CF 账号的起起落落。
2017 年 7 月 13 日，第 1 场比赛，Codeforces Round #424 (Div. 2)，rating 1408(-92)。
2018 年 2 月 14 日，第 12 场比赛，Codeforces Round #462 (Div. 2)，rating 1648(+85)，首次上蓝。
2019 年 2 月 23 日，第 26 场比赛，Codeforces Round #541 (Div. 2)，rating 1920(+43)，首次上紫，进入 Div. 1。
2020 年 1 月 5 日，第 34 场比赛，Codeforces Round #612 (Div. 1)，rating 2191(+94)，首次上橙。
2020 年 3 月 18 日，第 39 场比赛，Codefoces Global Round 7，rating 2393(+98)，历史最高 rating，离红名只差 7。
2020 年 4 月 3 日，第 40 场比赛，Codeforces Round #631 (Div. 1)，rating 2315(-78)，远离了红名，从此开启 2300 上下的苦苦挣扎。
2020 年 7 月 4 日，第 45 场比赛，Codeforces Global Round 9，rating 2120(-205)，历史最低 rank，我校历史最高掉分纪录，红名希望彻底破灭。
2020 年 8 月 12 日，第 47 场、最后一场比赛，Codeforces Round #664 (Div. 1)，rating 2218(+118)，终结。
将来肯定还有机会，但是高一阶段，NOI 前，OI 生涯的主线部分内，rating 变化曲线到此为止了。

8.13

上午 cz 模拟赛。T1 是非常简单的 DP 题，本来口胡完后就去想 T3 了，这时发现 swk,hyw 等人都已经切了 T2，刚准备回去看一不小心看到群里有人说“三元环”，恍然大悟，于是这题又被提示了。剩下的时间除了写了一会前两题之外都在想 T3，不知为何就认定这题不能 $\text{polylog}$，陷入了 $O(n\sqrt n\log n)$ 的泥潭。结束时和他们交流了一下才意识到可以用线段树轻松做到 $\text{polylog}$.

看成绩，还是 100+100+0，千篇一律的 rk10 左右。今天出现了省队集训里第一位 AK 神仙——dsq. T3 本不是什么难题，可是又成功被我想歪了。

下午 cz 继续讲数据结构，听得越来越意识模糊。更加坚定了 NOI 要被数据结构题搞死的信念。

晚上 hyw 提前回 qd 休整了，而我还决定继续在这里，直到最后一天。

8.14

前一天半夜就不时看到闪电击亮了夜空，却迟迟听不到雷声。上午是最后一场 OI 模拟赛，出题人是 zyb 学长。由于雨太大，且从宿舍到机房有近十分钟的路程，神仙们竟不约而同地没去机房，而我还是照常去打了比赛。
一进机房就听到 zyb 一句邪魅的“你好”，比赛中很长时间 zyb 一直坐在我旁边，还不时问我“你会不会 XXX 题”，使我倍感惶恐。T1 竟然是 $10^5$ 大小的进制转换，我大概 50min 的时候开始写 $O((\frac{n}{\log})^2$，还没开始写时 zyb 一句“T1 你再不会就不像话了啊”，刚写完第一行压位 zyb 突然一句“看起来你智商没啥问题”，又写完下一行 zyb 一句“但是能不能过这题就不一定了”，又写到主体部分 zyb: “你怎么开始二重循环了啊”，搞得我彻底懵逼。“难道这不是正解吗？”“当然不是啊……原来你也不会进制转换”“啊这……”
好，推翻重来。我并没有听说过进制转换有任何正经做法，因此挺长时间都不知所措，直到大约 9:15 发现分治 NTT 可以 $O(n\log^2n)$ 轻松解决。这应该是正解了吧，我果断开始写，9:55 左右写完，当然还是无法避免犯各种智障错误的结局。zyb 看我写完后，在 5min 内问了我三次“你怎么还没调出来”，大约 10:25 的时候发现我还在边擦冷汗边跑大样例，扔下一句“好我对你彻底失去信心了”。这种无地自容的绝望的感觉……真的……难以描述……
10:35 我终于调了出来，可问题远没有结束。我随手造了组极限数据，它磨磨蹭蹭地跑了 $14s$. 瞬间傻眼，急中生智，压位！改完后变成了 $5s$，正准备进一步卡常时 zyb 走了过来，我跟他说了现在的情况——我的本机很慢但不知道在评测机上能不能过，他让我发给他代码先帮我测一下。片刻后得知 0.7s AC 了，终于长舒一口气。
T2 又是大数据结构，T3 是智商交互。最后的时间一直在玩 T3 的 $K=2$ 分，想出了 4 种离谱的假做法，第 3 种在写到最后一点时恍然大悟“哦，不行！”，听到 zyb 一声冷笑“你也知道不行”。第 4 种写到最后一分钟，本以为终于能得分了，结果 zyb 指着我的代码说“你有一种情况假了——这里”，我定睛一看发现这直接导致了整个做法从头到尾崩塌。最后交了 $20$ 分暴力和这个有 $\frac{1}{8}$ 错误率（且能随手卡掉）的代码，面对 zyb 说“精心构造过保证把你卡到最劣”的交互库。

中午冒雨往返食堂，回来看到 result，什么，$100+0+40$？说好的“精心构造过保证卡到最劣”呢？我这明显错的离谱的算法怎么多跑过去 20 分？以及我为什么 rk1 了嘤嘤嘤？冷静一下发现只是因为 swk,tsx,lyh,smy,hyw 等一众神仙都没认真打，zyb 对此表示强烈不满（：

下午讲题发现 T3 是神仙的 IMO 题，zyb: “你们要看我现场切 IMO 题吗” 又简单讲了一下 TopTree、vEB、四毛子等高深的数据结构讲这个干嘛。除了被算法和数据结构中的神来之笔震撼，也被 zyb 的强震撼了，这大概真的是思维代码能力超高知识面超广的全能型选手。。。

8.15

APIO2020，NOI 的前奏。
上来开 T2，以为 $q\le 5$ 是白送的，只要判连通块内是否有环就行，写完后发现不会编译那种鬼畜格式的程序，大概设了半小时环境变量还无法编译成功，索性改成了输入输出测样例，过了样例却一直 WA0。后来意识到结论有重大漏洞，改成了判断有环或路径上有度数 $\ge 3$ 的点，又 WA 之后才意识到度数 $\ge 3$ 的点不在路径上也行，1h30min 才过了 37pts，可正常人十几分钟过掉完全不是问题吧，感觉完全不在状态。
又思考了一下感觉 T2 正解是数据结构并不可做，于是转向 T1，读懂题后想到 $O(nm^2)$、$O(nm)$，冷静了一会发现是 $O(n\cdot \max f(k))$ 的，$10^5\sqrt{4\times 10^5}$ 不虚，于是写完了，还不到 1kb，一发过了。2h30min，100+37+0，终于开始进入状态了. IOI 赛制令人舒适。
去看了 T3，发现 26pts 很白给，随手写了，3h 100+37+26=163. 然后我又一次犯了眼高手低的毛病，总想瞄准正解或者拿最高档部分分，做到最后却只想出一个 subtask3 的模棱两可的做法，以及只要我成功实现了这个做法再加三四行代码就可以过掉 subtask4。拿了 T2 的 6pts 裸暴力，还有 45min 时开始写 T3，最后又是标准结局，漏洞百出，颗粒无收。100+43+26=169 草草离场。
出考场后问了一下旁边的 swkdz，第一句话“我没 AK” 第二句话“今天全场 200+”。他 A 掉了 T2，并告诉我“Kruskal 重构树一下即可”。瞬间晕倒，我甚至在场上完全忘记了还有重构树这个东西……？
swk 100+100+47, tsx 100+100+47, dsq 100+100+0.
NOI 的前奏，凉凉。
作为我校唯一一个参加 APIO 的选手，光荣地被全场打爆，很遗憾又给母校丢脸了。

大概率是要 Cu 了吧，可能这次的表现还挺接近真实水平的？不满意是必然，但到此地步真的已经无话可说，毕竟冰冻三尺非一日之寒。
更何况 APIO，以及最近的一切，也都是 NOI 的铺垫。大赛在即，心态高于一切，即便今天被踩得体无完肤，唯一的出路也只能是明天重整旗鼓，走向 NOI。
下午，和 sddz 一起从日照回青岛，准备明天清晨飞往长沙。
那里，乾坤未定，尚有无穷变数。