CSP 半云游记

std__int64_t · 2026-11-01 21:00:41 · 生活·游记

初赛不想写。

你不让我在家 VP，我在学校 VP 总行了吧。

J

省流：分数符合开题顺序。

11:40 到的，12:20 开考。买了一瓶水和一袋士力架，说是怕考试时思掉，其实是馋了。

去年 AK 了，于是到开。大概 30min 的时候想到了一个做法，去维护留下来的卡牌组成的区间然后有点小问题。

我怕自己炸掉回来做前三题（也是倒开），T3 是一个很显然的从高往低的贪心，随便维护一下即可。T2 是一个很傻逼的打磨你，写了 20min 左右，T1 纯水，大概 45min 弄完了这三题。

*中途我的电脑显示器挂了，换了一个电脑。

然后回来做 T4，在原来这个做法的基础上面建个图拓扑（其实 dfs 都可以代替）dp 一下就做完了。

大概 2:30 的时候写完的，然后重测大样例，检查文件弄到了 3:10，原来可以提前交卷，交了。

然后呢？90+100+100+100。原因是 ABCDF 而不是 ABCDE，大样例没测出来我无疑是愤怒的，主办方的【】在哪里？

晚上电脑被 fm 收走搞文化了，第二天上午要 S。

S

因为各种各样的原因，爬克让我在家里自己断网测，7:50 吃完早饭之后 fm 物理断网之后用 QQ 给我发了个文件，开测。

T1 显然加到 a 中存在的值最好，排序后二分一下就做完了，大概 10min 写完的。

T2 注意到 d 很小，于是可以枚举开始和结束进的是哪条线，于是其他的步行全部集中在换乘，这个可以建图的时候预处理 i 换到 j 需要的最小步行次数，Floyd 以下即可。8:50 做完了。

然后开看 T3，这个大区认为 |E|=O(n^2) 的时候一次 bfs 的时间复杂度还是 O(n) 导致没拿到 n=5000 的分，其实线段树优化建图之后边数就控制在 O(n) 了，不过我为啥不写 /fn/fn/fn

然后想特殊性质 A，大概就是对于 i 只可能是 i-2k+1 有贡献，然后就做完了。

对于特殊性质 B 也是简单的，前半部分的连通区间为一个前缀 [1, pre_i]，后半部分的连通区间为一个后缀 [pre_j,n]，所以有贡献等价于：

根据单调性双指针即可，就这么写了 32 pts（我以为的 56 pts），但是 B 写挂了，我无疑是愤怒的 /fn/fn/fn

然后 T4 直接枚举子集写了一个 O(n2^n)，获得了高贵的 15pts 然后就检查直到下考。

最后得分是 100+100+32+15=247，应该没 7√ 了，不管了，反正是 VP。