NOIP 2024 游记 & 赛前训练

day -18（11.11）

今天做信友错的模拟赛。

第一题是和最短路有关的，看到 \(n\le 500\) 就想到了 \(n^3\log n\)，然而看了很久都不会做，于是果断火速打了 \(O(n^4)\) 的暴力走人，get 50pts。

然后看第二题，发现是最大异或路径，正好最近刚学了线性基，于是想到之前做的一道线性基的题目，把每个环加入线性基。然后就能做到 \(n^2\)，再补一个树的性质。get 55pts。此时比赛刚过一小时。

很快啊，其他人还在做 T1，我就开了 T3。看了一会想到用并查集维护，再记录修改前的以实现撤销。发现大样例都过了，此时我还以为复杂度是正确的，此时比赛刚刚过半。但是去了一下洗手间，就想到可以构造一条链卡到平方，这个做法只能过随机的性质和不撤销的性质。于是又补了链的性质。get 55pts。

此时光靠暴力已经得到 160pts 了。

比赛刚过半，看了一下第四题，觉得还是要先补一下第一题的性质，补了一个性质 A，多得了 10pts。

这时我去尝试想中间两道题的正解，无获，于是开始打最后一题的暴力。

后半程有点松弛。

发现暴力分很多啊，在最后 20 分钟写完了 \(n\le 9\) 的 40pts 暴力，然后又补了前两个性质共 8pts。

然后——比赛结束，最后一题 48pts \(\to\) 60pts，最后总分 \(50+55+55+60=230\) 喜提总榜 14，jz 第 3，原来是暴力场。

赛后发现 T1 是线段树分治的思想，还有 Floyd 插入单个点的技巧，我们只以一个点集内的点为中转点转移（插入顺序没有要求），就可以求出只经过（不包括起点终点）这个点集内的点的最短路。

T2 是线性基的结论，\(qmax(i\oplus j)=qmax(i)\oplus qmin(j)\)。

T3 是树剖+线段树的 4K 大数据结构，就是把轻链的贡献全部挂在重链上，有点类似动态 DP 那种。

T4 是论文题，用结论的式子计数。而暴力就是递归，然后在递归过程中进行剪枝就能跑得比较快。

总结：这场比赛时间分配还不错，前面暴力打得比较快，调试也没花多少时间，大概是经验越来越丰富了吧。但可惜后面充裕的时间内没有想出正解，其实正解是不难的，还有提升空间。