CSP-S 2022 VP 记

游记一直咕了没写，我得尽快把题解也给写了。

总而言之，不知不觉就已经九年级了，虽然我没有把这一年想的多么重要，但这也确实是生活的一个转折点，初中毕业后就又是一段新的征程。

其实现在去翻 oierdb 不难发现历来的成绩都差的离谱，今年本来是一个好机会为初中竞赛生涯争取一个看得过去的分数，但是由于疫情初中生参加 CSP 的资格在最开始就被砍掉了，我只能说动态清零不是什么好东西，另外也不知道今年 ISIJ 会怎么选，今年是最后一次机会，我觉得我还是有希望的。

晚上在洛谷上 VP 了这场比赛，来看看题。

T1 还挺好想的，由于要求经过点不同，所以不能够直接 dp。我们的路径是 home-A-B-C-D-home，考虑拆成 home-A-B 和 home-D-C，然后再把这两段路径拼起来。难点在于拼接，我们枚举 B 和 C，然后取出合法且权值最大的 A 和 D，但是这四个点可能会发生冲突，最劣的情况下，一个点会冲突两次，所以我们一个要存三个最大值，合并的时候枚举一下即可。

T2 很简单，我是用线段树写的，一次性可以处理更多信息，代码长度和复杂度会比 st 表劣，但是无伤大雅。注意极值会有点难处理，我最后还是特判了不存在的情况，或者你也可以用 __int128 就会方便不少。

然后先开了 T4，$k=1$ 就是树上路径长度，而 $k=2$ 时我们经过的所有点也一定在两点间的简单路径上，证明是比较显而易见的，假如走了简单路径之外的点，我们一定可以找到更优的走法。$k=3$ 的时候就可以走路径外的点了，具体来说，假如我们有 $a\to b\to c\to d\to e$ 的简单路径，我们可以在 $c$ 的领域内找不同于 $b,d$ 的一点，途径它从而越过 $b,c,d$，考场上我以为就这么一种情况，但并非如此，所以要重新设计 dp 状态。

$k=1$ 可以树上差分，但是我不知道为啥打了个树剖上去，还打错了。对于 $k=2$ 和 $k=3$，注意到在随机情况下树高期望 $\log$，所以可以直接把路径拎出来 dp，上面已经说到我 $k=3$ dp 是假的。最后喜提 32pts，实际上的期望得分是 76pts，很震撼。

当天状态不太行，浪费了不少时间，如你所见打了很多完全不需要的数据结构，T3 随便写了写，官方数据下 55pts，当然我现在发现我当时写的代码又是假的，如果改成对的就变成了 60pts，有意思的是我有一版错的代码跑了 70，利用众所周知的「不可以，总司令」可以拿到 80。

实际总分为 100+100+55+32=287，我觉得还是可以接受的，虽然上 300 并不困难。

差不多就这样，不想在这里写小作文，可能会 NOIp 之后写一点这玩意，不过也没人看，而且写小作文不怎么是好习惯。

最近 cf 打得不错，希望自己近期能有一个好的竞技状态。

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。