NOIP 2024 游记

$100+100+32+40$。 T1 上来读错题瞎写了 $20\mathrm{min}$，然后推了一段时间发现会做了，但是巨麻烦 没办法，写吧 于是写写写，然后调调调，在 $1.5h+$ 时终于通过了大样例 感觉大样例很强，且这种题不会有什么 corner case，且这种是一点错整个就错的问题，就没写对拍 开始看 T2，发现限制每个数可以取 $x$ 和限制每个数只能去 $1$ 等价 于是想到了 $0/1$ dp，就是记录当前有没有被限制 然后这个巨简单的式子又推了很长时间 先写了一个 $O(n)$ 暴力，调试又调了很长时间 过了该过的点 写成矩阵的形式，诶矩阵快速幂好像时间复杂度炸了啊 哦好像可以光速幂 于是写了 过了大样例，没管 开始看 T3 的时候，已经只剩 $\mathrm{1h45min}$ 了 想 T3。此时不自觉地将题读成了“有多少种 dfs 序” 然后发现这好像是跟括号序列有关的，推了一下卡特兰数，感觉是对的 为了避免正解写挂，先去写 T4 暴力了 T4 暴力写了 $n\log n+\sum(r-l+1-k)$，有 $40

链想了想，没有想清楚

感觉好像是二分再套主席树，觉得不如写 T3

T3 写完后，测样例发现读错题了

不同 dfs 序生成的同种树算一种方案

开始想暴力

k=1$ 是两边 $\prod \mathrm{deg}

观察大样例发现链是 1

菊花是式子

写完这些比赛已经快结束了

测了一下大样例，检查了一下文件读写

把 T1 的 assert 注释掉了

结束了

到 12.6 才知道自己寄的有多么彻底，还是在没有挂分的情况下

之前一直在想一个问题：T2 为什么直接容斥就可以了呢？

发现这是没有意义的，你再考一次，改写矩阵还是写矩阵

还有在想：之前模拟的时候都会给后面两题留出 3h 的时间，为什么这次不行了呢？

T1，也许再精细刻画一下，就算不是正解的思路，就会发现很多部分都是没有用的

T2，也许多练一练推式子，就能快速写出正解

然后，T3 没有看错题的话，仔细刻画树的形态，就能得到正解（或者大部分暴力）

T4 也许就那样吧。但是，如果知道相邻 \mathrm{lca} 的 trick（或者启发式合并维护 \mathrm{lca} 连续段的trick），快速用二维数点刻画，也许也不是不可拿下

再或者，给我大量时间去想 T4，考虑对虚树的刻画，相邻 \mathrm{lca} 也是可以直接得到的啊

这不应该，仅仅是我所能拿到的

以前以为的“远大理想”，现在都快是危机了

希望危机，可以带给人们动力吧。