CSP-S2022 游记

· · 个人记录

在 cnblogs 中阅读。

JS-00564 C276 旁边是两个妹子

上午到学校休息了一会，没有干什么活，为下午考试留足精力。

在学校附近吃过午饭就去华山饭店了。大概十二点五十到考场，发现没有座位，全是上午 J 组同学的吃着午饭继续考 S。所以我在门口晒了会太阳，一点四十到考场前排队。

进考场之后，发现比赛用机是笔记本，Fn 在左下角，Ctrl 在它的右边，右移键在右下角，PgDn 紧靠着它上方，键位分布非常阴间。写代码的时候感觉确实阴间，至少降低了百分之二十的代码效率。

两点半准时开考，顺序开题。

看 T1。首先想到可以对每个点对判断是否合法，但是直接 DP 不行，因为不能经过重复的点。那就枚举中间两个点，只需要知道从这两个点出发分别能到家的权值最大的三个中转点，枚举一下就行。十分钟写完。

看 T2，憨憨题。维护区间最小负数，最大负数，最小非负数，最大非负数，根据题意枚举即可。二十分钟写完。

读题想题测大样例一共过去了五十分钟。

看 T3。第一个条件包含于第二个条件，很迷惑，怀疑自己读错题了。所以先打平方暴力，能过大样例。想了想，发现不同出点的边相对独立，可以分开维护。但是判断度为 1 似乎非常困难。想了一会，根据只要求判定觉得可以直接 Sum Hash。维护了 30 个 Sum Hash，写了二十分钟左右。

两个小时不到，看 T4。一开始看成链，觉得是简单题，后来发现没这么简单。推了推发现只会走到与当前点距离为 1 的点，而我们肯定会选择权值最小的那个，设权值为 w。那还是简单题。写了五分钟，修了十分钟假做法，又写了十分钟，调了二十分钟过了大样例。

设 f_{i, 0/1/2/3} 分别表示到路径上第 i 个点 u，当前在 u 在路径上的前驱，距离 u 为 1 的点，u 以及 u 在路径上的后继的最小代价。我们无法知道后继权值，所以 f_{i, 3} 要减去后继权值，等到贡献到 2 的时候再算上。有转移方程

\begin{aligned} f_{i, 0} & = f_{i - 1, 1} \\ f_{i, 1} & = \min(f_{i - 1, 0} + w_u, f_{i - 1, 1} + w_u) \\ f_{i, 2} & = \min(f_{i - 1, 0 / 1 / 2 / 3} + v_u) \\ f_{i, 3} & = \min(f_{i - 1, 0}, f_{i - 1, 1}) \end{aligned}

倍增维护向上向下矩阵积即可。但是空间用了 2\times (18 \times (2\times 10 ^ 5) \times 4 ^ 2) = 1.152\times 10 ^ 8 个 long long，将近 900M 的样子，有点慌，但是问题不大。时间复杂度是 \mathcal{O}((n + q)\log n)，但是预处理的 n\log n 有 64 倍常数，回答询问的 q\log n 有 16 倍常数。在本机 i3 这种烂机子上大样例 n = 50000 都只要 500ms，那应该是没问题了。

三小时不到。好像 AK 了，非常感动。感觉今年这难度要 AK 一车。

花半个小时检查四道题，给最容易挂的 T2 写了对拍，然后罚坐半小时。

签完字直接跑了，也没管同学考的怎么样。听说 ycx csy AK 了，tzc T4 没过，lxr 晚节不保。ymx？笑死，ymx 忘报名了。

代码公示自测，每道题都过了。感觉很稳。