NOI 2023 Exploded

· · 个人记录

好像没怎么写过游记，这次还是写一下吧。

（其实我是写了省选游记的，从初三暑假一路写到省选。当时写完忘记发了，最近想起来找不到了……）

省流： 打出了一个 saber 应有的水准！

Day -n

天天模拟赛被吊打！以前的我可能还会有点情绪波动，现在我早已习以为常。心态就是这么练出来的！

Day 0

报道日，我忘了干了啥了。食堂是自助餐，还不错。

Day 1

早上是开幕式。感觉还行。

中午简单睡了一下就去试机了。试机题目是 NOIP 2021。给了一个 SelfEval 程序用于本地测试。还是很不错的，可能过几年就可以实行 IOI 赛制了！键盘熟悉了一会后就习惯了，打算把 T2 写了。写到一半开始笔试了，有几道题题库里面没有，但是挺典的。后面调了很久 T2，发现把 \le k 看成 =k 了……再打了几个板子就润了。

晚上提前了一会睡觉。结果发现被子很厚啊！一直处于盖被子和掀被子的循环中，然后就一直睡不着。最后一次看时间好像已经一点了……

Day 2

第二天醒来，精神比想象中的好。去买了瓶咖啡（丝 滑 拿 铁）。

开题，发现是计数场。

T1 很简单。写 + 拍完差不多是 1h。简单看了一下后面两题，打算先写 T3 部分分。

T3 O(2^k\operatorname{poly}(n)) 是简单的，有 36。A 性质写棵线段树也有 16。加起来就已经 52 了。T3 部分分这么多，看起来是简单场。又想了想 B 性质，感觉会 O(N^3) 的 DP。总共是 60 分。想不出来更多分了，就开写了。

结果发现那个 DP 有点假，修修补补搞了半个多小时。感觉是能改对的，但是当时脑子里面一片浆糊，最后竟然又换回了最开始的写法，然后又假了一遍。最后发现搞了这么久就为了个 8 分，于是愤然跑路！

此时只剩不到 2h 开 T2 了。前 35 分是容易的。想了想发现答案似乎和树的形态无关。做了会 K=0，发现可以先 DP 后再背包一下。就有 60 了。再写个多项式 ln 和 exp 就可以 70 了（？），可以 O(m^2) 实现。此时得分上限 222。当时感觉简单场不会 T2 有点寄，于是又想了会正解和部分分，发现啥也不会了。还剩 1h 的时候只好开始打暴力了。

感觉暴搜打起来很烦，就先打了 K=0。结果死活过不了样例……感觉当时的精神状态还是不太能调得动 DP。看了半天终于看了一下样例解释，发现一个地方想错了……又修了一下，还是过不去！只剩 20min 了，只好开始打暴搜。

然后发现暴搜也过不去样例！看了半天都不知道哪有问题，然后发现题读错了，T' 也要求 1 是根……然后就过样例了。加了个 m=0,1 的特判，=2 的都来不及加了……最后两分钟又改了一下 K=0，只能过小样例，那也没有办法了。

期望得分：100+25+52=177。下来一想，这不连最 saber 的暴力都没打完吗？？？你 5 个小时都干了些啥？？？

吃饭的时候，发现群里在说 T1 可以 x_1>x_2。大样例保证了 x_1\le x_2，我的 gen 也保证了……我：凄凉的世界走投无路了！

但是好像当时的心情意外的好，也不知道为什么。

下午查分，T1 没挂！但是 T2 暴搜挂了，难绷。看了半天发现两棵树的数组用混了。实际得分：100+15+52=167。感觉没有多少人 T2 能比我低了。

晚上去听课。发现似乎一堆人 T2 打表过了 70……而且那个规律好像打了就能看出来……后来想想，我都知道和树的形态无关了，那确实可以打表啊！至少能过 n=1,K=0 吧！哦，我暴搜都写挂了啊，那没事了。发现正经推 K=0 也很简单……还是我太 saber 了！

在 CQ 省队里好像垫底了。符合 saber 的定位！

感觉计数已经是我相对比较擅长的领域了，结果还是在计数场垫底了。Day 2 翻不了一点。

jzp 告诉我可以把被子的棉芯取出来。很有道理啊！

Day 3

早上似乎有个什么 NOI 嘉年华，但是我起床的时候好像活动已经结束了。

本来想着不睡午觉的，结果躺床上一恍惚 3 个小时过去了……

晚上又提前睡了。但是完全睡不着啊！可能是白天睡太久了，感觉人十分清醒。在思考睡觉的意义的时候突然想到，与其提前睡觉，不如熬会夜让自己困一点！于是我及时止损，在一点的时候刷起了知乎，大概刷到了一点半，然后不知道怎么就睡着了。

好像省选前两天晚上也是这个状态。但那时是有点紧张，而这次的原因有些抽象……上一次大考前睡得好还得追溯到春测了。

Day 4

早上起来，又买了瓶咖啡（仍然是丝 滑 拿 铁）。

开题，发现这回没有计数了。过了一会发现 T1 要取模，所以 NOI 考了 4 道计数！

简单看了一下部分分，发现 T1 能写 70。开始想正解，讨论了半天感觉很复杂。过了一会才想起来完全二叉树的条件（我甚至读题的时候都在旁边批注了……），于是对每个点的祖先链跑一下 Dijkstra 就行了。用个 ST 表找子树内的最浅边。O(2^nn^2)。然后就开写了。

写完后调了调，已经拍不出来了，但是仍然过不去样例 2……尝试了各种拍的方式都拍不出来，肉眼也看不出来。难道我就要整场耗在 T1 上了吗！发现样例 3 是 u=1。测了一下发现过不去！assert 了一下，整出了一些违背常理的东西。然后发现我 Dijkstra 每轮应该找没有访问过的点的最小值，但是我直接把初值设成了第一个元素，没有看它有没有被访问过……改了就过了所有样例。此时已经 2h 多了，我写这个 saber T1 竟然花了 2h！测了下极限数据发现能跑就没管了。

T2 是字符串，不是很会啊！还是先看了 T3 的部分分。

想了一会什么性质都不会，打了个 O(3^n\operatorname{poly}(n)) 和 w_i=1 就跑路了。能测的样例竟然只有 4 个 1，想了一下还是写了个大暴力拍了。

还剩 2h 看 T2。看了一会只会 O(N^2\log N)，A 性质看起来很可做的样子。

又想了一会，发现有个很好写的 O(N^2) 就先写了。

依然是什么性质都找不到，就开始写 A 了。直接枚举 LCP，最多枚举长度为 B。然后在 vector 里二分一下。B=30 应该就行了。写出来，发现好像跑得很慢……后面把 map 换成了离线排序双指针，还是只能过 50000。发现可以只用这种方法计算 \le B 的，>B 的把位置找出来暴力算就行了。这样 B 可以开到 12，感觉能跑。于是改了改。调到了最后一分钟发现新加的 map 忘记清空了，清空了就过了。但是跑大样例似乎变慢了很多？？？没敢粘上去。

期望得分：100+44+30=174。感觉，也是最 saber 的暴力都没打完啊？

下来突然想到，变慢的原因可能是那个样例只有前两组满足 A 性质，而我最后五组都跑了……不管了反正都寄了！

下午出分，没有挂。但是我把那个程序粘上去能多 12（

总分：100+167+174=441。排名接近 200 了。怎么感觉让一年前的我上都不止这个分呢？？？一年白学了！

虽然但是，在我的幻想中我已经 100+222+186=508 了！怎么还差 1 分啊？算了还是洗洗睡吧。

这种水平打什么 OI？我还是趁早退役吧！

Day 5

想了很多进集的分布，感觉都很困难。唯一有希望的就是 100+100+70+60+100+56+30=516……看来靠暴力还是不行，要切题啊！

加训！加训！加训！