CSP2026游记 [ Hexo ]

这几天乐不思蜀了，连 CSP 游记都忘记写了。至少从这一点来看，这里比 GW 是要更宜居的。这里有许多对计算机科学有基础、感兴趣的同学。我在 GW 已经找到了一种模式，在这里可以直接套用，就是在行政班上把人际交往最小化，在计算机科学特定场合发展深入的人际关系。

然后我在 CUHK 参加了第一轮，在九龙华仁参加了第二轮。第一轮很容易就通过了，没有复习。第二轮前夜，我仔细复习了各种数据结构与算法，包括稀疏表、莫队、单调栈单调队列以及 PBDS 的平衡树写法。算法主要是最短路，包括 SPFA 和 Dijkstra，一直到凌晨。实际上，这几天我都没早睡过。然后第二天就用上了。

考试机是纯正的 NOI Linux，没有 Windows。不同于内地，本港 CSP 的代码不是离线收集，而是在线提交。我也不知道有没有网关，因为我不敢以身试险。赛制还是一样的 OI。我最终决定使用 Emacs 编辑代码。第一题第一眼看上去是一个过程题。我以为从第一个开始选总是最优的，差点就信以为真了，好在被最后一个样例证伪了。然后我对着硕大的大样例冥思苦想，后来好像是构造出了一组数据，证明了从第一个开始选并不总是最优的。于是便快速写了双指针，考虑到左端点不变的情况下，右端点越往右越优，同时在排序完序列后，由于左端点比右端点小，所以左端点往右走一定会减少费用，所以之前的右端点放到现在一定合法。维护一个前缀和快速计算区间和，再遍历左端点，贪心地找右端点，记录最大窗口即可。

第二题失手的主要原因是错误估算复杂度，把 $n+(n-1)+(n-2)+\dots+3+2+1$ 误以为是 $n!$ 了，导致我否定了依据换乘站建边的想法。不过我直到不久前才恍然大悟 Dijkstra 的 $O(V(V+E)\log(V+E))$ 在如此近似完全图的密集图上是比 Floyd 的 $O(n^3)$ 更劣的。所以就算我正确地计算了 $1$ 到 $n$ 的和，严格意义上讲我也应该 TLE。不过据说 CCF 故意放行了这种做法。我最终给出的做法是把地铁站和地铁线都变成图上的节点，变成一个类似于细分图的东西，总之是一个二分图。然后对于每条线跑 Dijkstra。对于 $t$ 相等的数据，把 Dijkstra 换成朴素 BFS。理论极限得分 76，自测与实际得分 60。

第三题没看懂题，我以为只有一种可能的解，就是形如 $A\dots B\:C\dots D$ 四个点，其中 $a+k$ 最远可达 $C$ ， $d-k$ 最远可达 $B$ ， $B$ 的左边一个点加上 $k$ 到不了 $D$ ， $C$ 的右边一个点加上 $k$ 到不了 $A$ ，统计对于每一对 $B$ 和 $C$ ， $A$ 的个数乘 $D$ 的个数的和。虽然我至今还没有理解或尝试去理解这道题，但是居然骗到了 5pts，可喜可贺。

最后一道题写了一个 $O(\binom nknk)$ 的暴力，核心就是选的点越多越优，然后并查集验证联通块数量，然后统计每个点到每个选中的点的路径长度的最小值之和，这里的 Floyd 是预处理的，水了 15pts。

合计 183pts。

除了我，还有一个人没有上 200。他是被我称为“稳定发挥之神”的 lch。第二名反而是 zxh。实际上，这个排名在某种程度上来说可以算是在意料之中。我的家长们在讨论原因时，我告诉他们我大概知道原因了，其实不是 zxh 赶超，而是别人落下了，剩下的无可奉告。事实上，无可奉告是假的，而别人落下了大概是真的。大家近期应该还在沉迷于 florr，他们中等级最高应该还是 lch。而 zxh 亲口告诉我，他认为 florr 一点都不刺激，他还是喜欢三角洲。而三角洲几乎没有条件在系统会重置的机房电脑上玩，更不可能在系统不能重置的机房电脑上玩，所以他也干不了什么别的事。zjb 爱好就多了，看体育、看百度首页的新闻、玩 squares，时常也会玩 florr。难道颓废真的开始影响成绩了？我感到无奈，而我真的无可奉告了。

dc 未参加。