NOI 2023 游记

_yjh · 2023-07-26 22:13:35 · 个人记录

可能从 day1 出场开始就已经输了，day2 又算得了什么呢？

Day0

上午在背笔试，下午试机，AK 了笔试后随便打了点东西就回去了。晚上打了点轻量级的板子，也就是平衡树、ACAM 和 SAM 之类就睡觉了。当然了，没有睡着，这直接导致接下来的崩盘。

Day1

看了一眼 T1 就会了，开始写。预计一个小时左右就能写完。但喝了咖啡后仍旧越写越困，迷迷糊糊得写了 8.9k，此时已经过去两个小时，好在没怎么调就过大样例并且拍上了。

开始写 T2 暴力。上来直接把题意转化错了，不过对着错误的转化写仍旧过了小样例。然后开始拼性质，按我的转化编了几个特殊性质的做法，感觉有好多分就开始写。调了半天都过不去大样例，于是拿我的几个暴力互相拍，没想到拍上了。但此时我仍坚定认为是自己写挂了，可是调了好久依然过不去，根本想不到从一开始就转化错了！最后剩 15 分钟冲了一下 T3 的 24 分暴力，但由于代码能力不够，写完了但是挂了。

最终 day1 荣膺 100+5+0。在打表哥人均 T2 [50,70]，再拼上 T3 [36,52] 暴力的 day1 打成这样实在可笑。可谁让我暴力是错的呢？最终就是要接受分数只有暴力哥一半多一点的事实。总之连个题意都转化不对，只能说是技不如人啦。

Day1.5

补了一天觉，晚上凌晨才睡着，不过还好。

Day2

开场先开 T1。由于忘记了线段树子树大小和是 O(n \log n) 级别的，感觉很不可做。不过把边反向了一下，发现复杂度就对了，仔细分析了一下感觉已经做完了。大概写了半个小时就写完了。结果由于两个地方把节点深度和节点编号搞混了，自己造的小样例又卡不掉，只好对着好几百的大样例生调。调了半天终于过了第二个大样例，一测第三个大样例 TLE 了，再冷静分析一下有一个地方复杂度分析错了，出去走了一圈，发现只需要将边按 u 的编号为第一关键字，以 dfn_v 为第二关键字排序，可行的转移便只能是一段连续的区间。使用 ST 表维护 dep_v+E.val 的区间 \min 即可。花了一会拼了个 ST 表，很快调完了。然后去写 T2,T3 暴力，没什么波折。

总之没挂分，100+40+10。如果不是 T1 不调那么久或许能更高吧。听讲评感觉 T2 很有趣的样子，而且确实是可做题，感觉有点遗憾。