CSP-S 2023 游记

赛前拿到了 4 种不同的糖，不知道大家怎么这次都想起发糖了（

开场看到了 struct，感觉是个模拟，那既然 T3 放模拟那应该过前三题难度不大（？

四题 1 秒 512 MB。

T1 大概用了十分钟，感觉过了样例就没什么可挂的点了。

T2 一开始就想到了拿一个栈匹配，之后误认为每个字符只会和下一个相同字符匹配浪费了一点时间想一个奇怪的双指针做法，后来突然发现是不是只有从 $1$ 扫到 $n$ 时，$l-1$ 和 $r$ 时栈状态完全相同区间 $l,r$ 才会合法。

写了个双模哈希在 50 分钟左右的时候过了大样例，但跑了 $1.3$ 秒，这个既然是哈希那是不是直接拼起来放到 unordered_map 里也不会被卡（考前背的 xorshift 忘了 /ll），大概跑了 $0.6$ 秒。

看了 T3 发现真是模拟，但没看数据范围以为 $n$ 是 $10^5$ 于是不会做，想不到怎么在类型构成的树上快速定位一个内存的位置（哦现在想起来如果 $10^5$ 的话根本没法输出吧（）。

于是去看了 T4，这时候扫到了 T3 的数据范围发现直接模拟就行，但感觉有点麻烦于是还是先去做 T4。

受到了这道题的启发想到了二分，然后因为每个点长的高度只和当前时间有关那是不是再对于每个点二分一次求出最晚种的时间就行，那菊花图就是直接排序，发现每个点的时间还需要对所有儿子 $-1$ 取 $\min$，那好像就没有祖先关系的限制了，直接排序就行，$10^5$ 两个 $\log$ 应该能过。

大样例跑了 $0.6$ 秒，虽然数据范围不是满的但也问题不大（？

这时候大概 $1.5$ 小时。

之后去一点点写了 T3，过样例的时候大概是比赛开始后 2 小时多。

然后不知道接下来要干啥了（

检查了许多遍文件名、数组大小和编译，怕不小心敲进去什么字符 CE 了。

---

好像在洛谷上 T4 被卡常了，但其他 OJ 都过了（

赛时没想到我的运行时间可能跟数据强度有关，于是检查两个小时也没想到给 T4 卡卡常 /kk

希望 CCF 数据水一点。

2023.10.29 upd: T4 过了，洛谷最大点 967ms （