CSP-S2022 vp 游记

__vector__ · 2022-11-05 15:42:26 · 个人记录

坐标 SD，因疫情没去成，就在家 vp。

开始 vp，先通读题面，看 T1 貌似可做，应该是 dp，就把想法写了下来，然后去看 T2。

T2 看到一个 “策略” 先是很震惊，T2 就出博弈论。结果仔细一看，每次只进行一轮。那不就成水题了，分析了一下，得出了一个需要分正负讨论的 O(n \log n) 做法，用 6 个 ST 表进行维护。

然后开始写。

经过大约 0.5h，写完了，一测样例，第一个样例过了，但第二个没过。看着 150 行左右的代码，感觉很寄。

没办法，去查错吧，用了 10min 左右，发现查询部分少写了一个，修改之后通过样例。

然后紧接着通过了第一个大样例，然而第二个大样例 RE 了。

看了一下代码，并没有发现数组开小，有些紧张。又看了 5min 左右，发现 ST 表忘判越界了。

修改之后通过所有大样例。

然后开始刚 T1。

我快速写出了一个 O(n^2) 的 dp 做法。

写完之后发现没过样例。

把样例画了出来，思考了 20min，发现 dp 转移方程错了。

然后紧急改，增加了一维状态，但还是 O(n^2)。

改完之后过了两个小样例。

但是大样例死掉了。

发现是少计算了一个点，但是不知道怎么改。

经过 20min 的思考，发现我的状态没错，但是转移有问题。

又改了改，但大样例还是死掉。

最后放弃了这个做法，去写暴力。

暴力还是比较好写，我很快就写出了一个 O(n^4)，使用 floyd 预处理然后暴力枚举四个点的做法，顺便加了一些剪枝。

然后扔掉 T1。

之后去看 T4

读完题，先去解决最简单的 k = 1。

这种情况下不能跳点，所以用树上差分 + lca 就行了。

用了 10min 写完树剖，解决掉了 k=1，复杂度 O(n \log n)。

看 k=2 和 k=3。

发现可以在树上进行 dp，我赶紧写完了一个简单 dp，一测，发现大样例挂了。

经过分析，发现我的 dp 少计算了一些东西。

然后进行修改。

又过了 10min 左右，过掉了大样例，此部分复杂度 O(n^2)。

然后去看 T3。

暴力死活调不出来，在调试过程中比赛结束。

70 + 90 + 0 + 36 = 196。

第一题可以说是暴力出奇迹。第二题不知道原因，WA 了两个点，T4 正常。

不知道如果 SD 正常举行，能不能省一。

官方数据：70+95+0+36=201。
~~如果正常举行应该有蓝钩吧........~~ 看这样子蓝钩线得上 300

过 6 级线了