2026 CCPC 南昌邀请赛 游记

热身赛

神秘热身赛，我们人还没到南昌，board 上就看到 AC 记录了。

到场后发现可以登录另一个队的账号交题，有点搞。

好在正赛时，锅没出在我们身上。

正赛

一学期没写题，导致整场都在犯糖。

正序开题，A 看着像不简单的 DP，skip。B 看着就很典，想了几分钟，想到了这些东西：

• 题目自然就是在路径上找一点，自然要选以为根，且不在和分支的最长链的末尾。目标是最大化。
• 要用换根 DP 之类的东西处理 top3 长链，而且还要讨论分支。
• 要查树上路径，免不了 HLD，然后还得考虑拿什么数据结构来维护树链。

感觉思路方向应该是对的，如果是平时，给点时间慢慢写应该能写出来，但以我目前的实力，赛场上不可能和这个题死磕。skip。

C 题一眼不可做。

此时看榜发现 L 已经过了一车，心急如焚，只瞪了一遍样例就以为答案是，抢过队友 A 的机子（他在写 G 题）一提交发现 WA，一下子失去冷静，然后马上想到的答案应为，以为只要特判就行，然后再 WA 一发。。。经队友 B 提醒才想到奇数无解。

签到题吃了发 WA，心态有点崩，回去开别的题。队友 A 很快写好 G，一提交，WA。检查发现循环小写字母，上界是，写成了。修改后才 AC。

此时我觉得目前能开的题是 HJK。H 因为，想到双向搜索，然后暴力合并，复杂度理论上是过不了的，但想不到别的更好的做法，且剪枝条件感觉挺强的，就上手开写。刚开始忘记考虑合并前两个块内各自的答案，爽吃发 WA，队友 B 来帮忙调试才发现。改完交上去变 TLE 了，因为我是拿 map 存的答案… 改成 vector 终于 AC。

两个队友讨论出了 D 题的做法，由队友 A 上机写，一发过。

此时才开赛 80 分钟，本来时间还挺充裕的，队友 A 开 A 题，队友 B 开 J 题，我开 K 题。

A 题队友 A 写出了很复杂的转移方程，但过不了样例；J 题和队友 B 讨论了下，打算拿滑动窗口 + 平衡树来做，但因为没怎么写过计算几何，差点连坐标转极角都不会。K 题我想简单了，以为只要从起点出发 BFS 求连通块，从终点出发 BFS 求连通块，最后遍历每条狗，枚举其视线上的点，判断该点是否一边是且一边是，将此作为合法的判断条件。

代码有点恶心，写完调半天，打印代码出来瞪，让队友 A 写 A 题，但连 WA 两发。

上机调，能过样例了就交，然后吃了几发 WA。

经过一番思考，意识到只判一个点的两边是不行的，因为可以有这样的情况：沿着视线走。

S.#
#.#
#.E
#U#

改，判断和是否都接于视线两旁。

还是 WA。

马上意识到忘记判断视线上的点是否同时属于别的视线了，比如：

S.#
#.L
#.E
#U#

那就分段，遇到视线上无法走的点就清除和的出现状态。

依旧 WA。

好在队友 A 发力，把 A 写出来了。然后让队友 B 写 J 题，我把 K 题代码打印出来，一行一行看。队友 A 再去看 E 和 I。

发现 K 题还真有个地方 typo 了，改掉，但提交还是 WA。

剩半小时的时候才意识到 K 是一个连通性问题，只看起点和终点所在块是不行的，因为视线的取消可能把一些空地块连起来，使得起点和终点所在的块能够间接地连通，比如：

###D##
S.....
#####.
E.....

马上想到先 BFS 染色，然后用可撤销并查集维护块的连通性。记得洛谷上有模板题P3402 【模板】可持久化并查集，但我没有准备这个板子…

当时队友 B 提到暴力撤销，但我脑抽了，以为复杂度不对（实际上每个点最多邻接于条视线，因此每个点并查集的操作次数是均摊的，但我脑抽没想到），没敢直接写。此时我们有个选择，由我改 K，或由队友 A 接着写 J，我的信心已碎了一地，所以没打算写了。但队友 A 最后也没写出 J。

赛后

最搞的来了，赛后看榜才发现还有个 M 题，DOMJudge 上的界面显示不全，得拉滑动条才看得到… M 题一眼秒了，二分答案转判定就做完了。然后题是银牌。或者，如果签到题没犯糖吃那些罚时，快也有银。

丢掉金牌就算了，银牌也丢了。

去年打的场区域赛，因为题目太阴间被创飞了。这场赛题明明非常友好，但因为疏于训练，战绩惨不忍睹。

越来越觉得我不适合打 XCPC，唉。