CSP-S 2024「 通过 T2」游记

Day -1

怒写 16 道板子，包括但不限于 SAM Dinic PAM。

同时升级快读中，因为快读字数不是整数纠结了很久，成功把我写 FFT 之类的时间占掉了。

一直在听水水的歌，切换到 mmr 状态了。

Day 1

T1，贪，10min。

T2，讨论加速度正负，一个区间内能被检测，然后是区间最小点覆盖。

由于 > 才算超速，写了神秘 eps 和 long double。

还有一个重量级的 const int eps = 1e-10，感谢 -Wconversion 的警告。

用时 1h。

完全没注意是不是要 long long，但是赛后看了不用。

T3，因为有一个颜色必定在 i-1，所以状态是 O(n) 的，转移就是一个全局加单点取 max，20min。

现在我觉得我要 AK 了，但是不急。

T4 题意比较长，但是时间还是充裕了，读题读了 30min。

那反正就是已知的部分只会有一个固定的 winner，先预处理一下，过一下性质 A。

调了一会，因为把 i 写成 k 了。

都不知道的部分是都可以 win 的，然后中间还有一个混着的。

然后就从混着的部分往上跳就好了。

开始写，但是写成了已知的最后一个跳，比较麻烦，后来改成了从未知的第一个跳。

现在大概距离结束还有 1h30min，优势在我。

那么要判断一个混着的能不能输，如果有未知的在里面或者已知的存在会输的就会输，赢同理。

写的时候突然感觉假了，但是这是幻觉。

反正最后用了个堆去维护，复杂度 O(tm \log n \log \log n) 就这样吧。

然后在距离结束 35min 的时候调过了，但是只能跑 t=16，卡常后跑 t=64 只要 1.3s。

溜达了一圈回来去了个重，就只要 0.8s 了，就当我 84 分了。

似乎比一些单 \log 快。

但是其实唐完了，能不能赢只和存在性有关，把存在性压位之后重新统计一遍贡献就是单 \log 了。

不挂的话 384，可能这将成为我唯一一次在正式考试通过 T2，T4 真的不会投降了。

没挂。