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，那应该是没问题了。
- 比赛结束后和 csy 交流发现他的矩阵大小只有(3)，记录当前点子树内距离当前点为(0, 1, 2) 的最小代价，在 LCA 处讨论一下，很巧妙！
- 树剖 + 线段树 + 预处理重链顶到每个点的矩阵积，可以将预处理常数变成(16)，但是码量较大。
三小时不到。 好像 AK 了，非常感动。感觉今年这难度要 AK 一车。
花半个小时检查四道题，给最容易挂的 T2 写了对拍，然后罚坐半小时。
签完字直接跑了，也没管同学考的怎么样。听说 ycx csy AK 了，tzc T4 没过，lxr 晚节不保。ymx？笑死，ymx 忘报名了。
代码公示自测，每道题都过了。感觉很稳。
Original: https://www.cnblogs.com/alex-wei/p/CSP_S2022_travel_notes.html
Author: qAlex_Weiq
Title: CSP-S2022 游记
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/642799/
转载文章受原作者版权保护。转载请注明原作者出处！