HNOI 2022 游记

· · 个人记录

Day 0

上午改题没改出来，下午敲了点题，补了下 public round 。

晚上看了下总结和做题记录，还有 trick 合集。

Day 1

去的比较早，听了一会儿音乐才进去。

大概 8:25 解压看题，粗略看题面很长，有点被吓到。先读题，看 T1 发现是模拟，看 T2 好像是常规计数，T3 看完感觉出题人可能有点大病（bushi）。

花 1h 小心翼翼地写完了 T1，感觉没啥问题。

接着看 T2，想了想只会 O(n^4)，大致思路是先枚举路径然后分段拉插，意会了一下感觉没什么毛病，后来的做法大概都要依赖这个，就先写了，细节比较多。

写完后调了一下就过了前两个样例，然后死在第三个样例半天，发现没有算区间完全包含的情况，赶快加上就过了。补了个线性拉插，但是还是要跑巨大久。

一时半会不知道怎么解决，看起来也没有什么可以优化的地方了，去再读了遍 T3 题面，感觉还是很恶心。由于时间并不多了，考虑了一下 T2 的部分分，发现没有几档可以写的，拿分还得从 T2 拿。

去洗了把脸冷静了一下，发现路径可以一起考虑，于是将分段提出来，拉插也提出来，稍微改改又过了大样例。接着解决一个路径权值积之和的问题，第一时间想到的是点分治（捂脸），写一发要跑很久，于是建了棵点分树，剪了下枝优化了下取模，好像怎么跑都只要 1s 多点。

看也没多少时间了写 T3 也没有意义，于是就多检查了几遍，然后下考了。

下考后发现大家考的都不是很好。去找 cxy 说 208，对了下 T2 做法发现我多了个 \log，直接换根处理就行了。对了下大样例的时间发现我起飞了，好像也没有什么想法，摆烂了。

下午回学校搞颓，跟朋朋、diwanul 打 gen，还看了下终炽（被优整的血压有点高，后来想到毕竟人家也才 16 岁而已）。

偷偷测了民间数据发现没什么问题，心态稳健。

Day 2

去的仍然比较早，于是又听了下歌。

发现今天题目画风正常了些，读题感觉 T1 应该是最简单的，T2 是神秘题，T3 看起来就不是我会的东西。

于是先做 T1，刚开始反应了半天没有反应过来，后来发现只要保留小于等于 43 的质数容斥就行了，大质数不会相互影响，于是写了一发过了样例，调整质数上界后仍然没问题，造极限数据跑，发现跑的很快，于是没管了。

接着开 T2 发现做的操作就是建树，然后合并成一条链，除了 x1y0 的情况都很好做。x1y0 想了一段时间发现不会做，看了下部分分感觉上有 48pts，于是先跳去看 T3 。

T3 思考了大概 20min 认为应该是不会做了，也不想再浪费时间，冲了一个指数暴力，洗了把脸，看起来还有 2h 多点，决定认真冲 T2 。

先将除 x1y0 的其他情况都写了，但是仍然做了很久还是不会 x1y0，后来感觉上算是灵机一动（其实是不知道在干啥）想了个神秘做法（upd：当时以为是真的 .. 下午觉得假了，过几天又发现确实是真的），以为很真于是直接开冲，写了个 O(n^2) 出来过了答案为 1 的小样例（捂脸），然后观察了一会发现分段做用线段树维护答案好像就行了，在脑子里过了一遍历史值的做法就开冲了。

很有精神。按照正常剧本最后当然是没冲完交了暴力，交的还是原来的那个 O(n^2) 。离场的一瞬间感觉有点后悔，早知道这样还不如老老实实把暴力全部写满呢，按照现在这样 T2 得分变成 eps 了。

出来发现大家考的都不是很好，朋朋貌似没能翻盘成功（祝好运）。cxy 说他 T2 写了个随机化，还说 zxy 把 T2 过了，感觉很顶。

下午没回学校。三点看 QQ 时发现有网友讨论 T1 是不是要去重，看到这句话冷汗直接冒出来了，回忆了一下好像题目没说是不同的质数，完蛋，小图灵直接爆出 35pts。到晚上一直情绪都比较激动，后来好像摆了。

Day 3

搞了下 whk 。

Day 6 4

搞了下 whk 。

小区门口新开了个卤味摊子，味道不错。

到 18:00 差几分钟的时候，IrisT 说公告改了，18:00 出成绩。

去官网看确实改了，下了个数据测了下 d2t1 发现好像没出事！顿时有精神了。后来小图灵跑完发现其他分数都没挂，看起来还行。

最后

sto zxy cxy 。

虽然考的并没有很理想，但是总算是中断一年以来的低迷状态了（指从去年 noi 开始一直寄 /kx，这也是为什么没有 csp 和 noip 游记的原因，根本没心情写）。

继续加油。