NOIP 2024 游记

· · 生活·游记

估：100+100+56+100=356

发现有一个题的样例高达 12 个，感觉是防 AK 题，应该比较难。

冷静思考几分钟发现是个贪，手玩挺对，但是不好写。写了 $10$ 分钟后样例输出 $3$。 细节处理出现了问题，改一改过了小样例和大样例，成功签到。 看到 T2 感觉这题也太傻了，手推了一个段内的式子，乘起来就行，$10$ 分钟写完过掉大样例。 看到 T3 发现题面很长，而且这就是 $12$ 个大样例的那个题，感觉不是很能做，仔细读了题发现可能只会爆搜分，先 skip 掉去做 T4。 T4 仔细思考一下可以树上 dsu 维护连续段，然后上个整体二分就做完了，但是 2log，视常数 $[64,100]$。写，调过第一个样例后第二个样例全输出 $1$，果断重构 ODT 之后过了前 $3$ 个样例，测第 $4$ 个，$1.8s$ 跑了出来，diff 发现有一堆查询错了，而且差的不超过 $30$。 上个厕所发现 ST 表中因为下标从 $0$ 开始要预处理到 $\lfloor \log_2 (n+1)\rfloor$ 而不是 $\lfloor \log_2 n\rfloor$，怪不得，只有 $2^k-1$ 才会出事，改了之后过了大样例。 去做 T3，仔细思考发现 $k=1$ 是显然的、链是简单的、菊花的式子也好做、然后想了 $k=2$，会了，但不会推广做法。不得不 $56$ 分跑路。 给 T1 写了拍，之后发现自己 T2 的用时过于危险了，把 map 换掉之后用时 $0.95s\to 0.2s$，放心了。 自己感觉没啥问题啊，只要 T4 不卡双 $\log$ 就行。