NOIP2025模拟赛4总结

liujuhan · 2025-07-16 23:07:45 · 个人记录

NOIP2025模拟赛4总结

T1

套了好几层操作，先摸拟下样例再说。

感觉只需要求出 min 和 max 就可以求出答案。

打个暴力验证下结论，应该是对的。

好像可以用回滚莫队，但是这是 T1 。

听说有人很快过了，应该不会太难。

原来|b_i| \le 10，那肯定要用桶。

好像直接贪心就好，过大样例了。

结论挺好证的，只需要让负数区间不断移动，就可以保证 min 和 max 中的每一个值都能取到。

赛后发现回滚莫队好像假了，需要带个 log 。

T2

字符串？有些像 AC 自动机。

不太对，需要不断更新 fail 树，直接退化成 O(n^2) ，只有 20 分。

听说有人用 SAM ，还有人在 fail 树上套数据结构。

用哈希可以暴力 20 分。

好像可以根号分治。

大样例还挺快，空间好像也不高。

赛后发现只有 20 分，其他点T或M了。

感觉是倍增，但好像很奇怪，为什么会移动啊！

这怎么倍增啊？

打个暴力先跳了吧，估计有 20 分吧。

赛后发现 30 分，挺好的。

正解就是神奇倍增，加个偏移量，然后再二分一下。

倍增还能这么玩啊！

T4

转换下题意，好像不难，上个线段树好像就没了。

先打个暴力吧。

暴力怎么 WA 了。

算了，放弃了。

赛后发现题意转换错了。

正解是平衡树，用时一天，学了 FHQ-Treap 的基础内容。