NOIP 2024 游记

· · 生活·游记

Day 0

进行了 1v1v1v1 和 2v2。A 见过原题，然后被 C 击败了（不过看完 G1 题解之后很快就会了 G2 和 G3）。

Day 1

大概 8:25 的时候发试题解压密码。大概是 T1 20 min，T2 15 min。

然后开 T3，想起了 ZJOI 2018 线图（不过两题好像没有任何关系）。不知道为啥硬把这题套了个圆方树去想（原树中边为圆点，点为方点），然后发现其实就是对每个方点周围圆点进行一个排列。然后稍微容斥一下，大概式子就推完了。很明显，可以用换根 dp，但是我考场上写了点分治。总共花了 70 min 左右。

开 T4。考场上忘了相邻 LCA 的深度 min 的性质，甚至忘了可以固定一个公共点然后找深度 min，于是直接开始大力上主席树，更新一个点的时候直接继承重子树并暴力更新轻子树，然后查询时直接二分。大常数双 \log，但是一算怎么空间炸了。不急，我们发现满二叉树会把链剖卡满，但是每次深度变化时如果把所有操作一起处理在满二叉树上会有非常良好的表现！于是直接开写，空间复杂度是啥我也不知道。常数瓶颈在于查询，需要二分深度，所以链跑得很满。大概是能过所有 10^5。

然后拼了一个 B 性质，期望得分 100+100+100+64=364。运气好可能 T4 能多拿点分，运气不好可能 T4 写假了（据说大样例很弱）。

Day 3

去 CTT 了。