CSP 2025

· · 生活·游记

CSP 2025 总结

今年只参加了 S 组，但挂的分比前两年四场加起来还多。。

总的来说还是决策失误。

最近 10 场校内模拟赛频繁挂分，于是每道题只是按教练 cpp 说的打好每个部分分。

显然这场比赛的几个部分分基本上都比较好想，但是不太好写，

考场上完全不在状态，出了考场才发现自己竟然调了 4 个小时的暴力，甚至 T1 的正解都没敢往上写。

于是就获得了一个极低的总分上限： 70 + 64 + 30 + 8 = 172 。

T1 \color{#52C41A}\text{club}

我要知道这题是 \color{#52C41A}\text{绿} ，就直接冲满分了。。

还是非常老实的先敲了三进制枚举的无脑暴力，大概就用了 5 分钟的样子，掐指一算应该有 4 个点。

然后先去看了特殊性质 A ，非常明显，把所有 a_{i,1} 排序取前 \cfrac n2 大即可，再拿一个点。

接着是特殊性质 B ，直接钦定所有成员都分进部门 1 ，然后把所有的 a_{i,2} - a_{i,1} 排个序取前 \cfrac n2 大即可。

似乎没有什么特殊性质可以思考的了，于是尝试从数据范围中找突破口。

直接考虑 dp，其实我原本还想写记搜拿来拍的来着

令 dp[i][j][k] 表示第 1 个部门已经分配了 i 人，第二个部门分配了 j 人，第三个部门分配了 k 人，对应满意度的最大值。

填表也能写，但是保险起见还是写了刷表，

转移方程

\begin{cases} dp[i][j][k] + a[i + j + k + 1][1] \rightarrow dp[i + 1][j][k] \\ dp[i][j][k] + a[i + j + k + 1][2] \rightarrow dp[i][j + 1][k] \\ dp[i][j][k] + a[i + j + k + 1][3] \rightarrow dp[i][j][k + 1] \end{cases}

时空复杂度均为 \Theta (N^3) ，应该有前 11 个点。

这样前前后后加起来就有 70 pts 了，但是时间也已经过去 70 min 了，所以处于性价比考虑，只能暂时搁置正解。

其实此时我想到了两种优化的思路，可能成为正解：

  1. 一般化特殊性质 B 的代码，将所有人先钦定分进部门 1 ，然后将所有人转移到部门 2 和部门 3 的代价较小值记录下来排个序，取前 \cfrac n2 小或者将所有代价为负的人转移走即可。

  2. 贪心，将每个人归进各自满意度最大的部门，最后最多只有一个部门超过 \cfrac n2 人，

    然后把该部门中每个人转移走的最小代价排个序从小到大取即可。

    此时有一点非常关键，那就是将这些多余的人转移走后，不可能造成另一个部门人数超过 \cfrac n2 。

    However $ 考场上没想到，还以为做法假了，就没写 $ \cdots

显然两种方法都已经非常接近正解了，但是还是决策上的问题，最后正解没有交上去。。

实际得分： pts70 。

T2 \color{#3498DB}\text{road}

这题题目有点绕，一开始还把乡村和城市的两个概念看错了，不过好在读了 5 遍题目之后还是理解了。

先考虑无脑暴力，对 m 条边先跑一遍 MST 还是非常一眼的，所以 m 的范围就可以直接优化到 \Theta (n) 。

然后 2^k 枚举计划改造的乡村，再加入对应的边跑一遍 MST 即可。

考场上调这个暴力调了将近 1h ，最后发现是在跑 MST 时有一些乡村仅与一个城市相连，造成了多余的贡献。

但这种情况理论上会在统计答案时被松弛掉，不知道哪里写挂了 :=)

总之最后这题的暴力也是无疾而终，不知道能不能水到 16pts 。

时间复杂度是 \Theta (\alpha M \log{M} + 2^k(k + \alpha nk \log{nk})) ，理论上有 12 个点， pts13 \sim 16 很悬。

然后把目光投向特殊性质 A ，将所有边放进去跑一遍 MST 即可，反正城市化不要钱。

这样的复杂度是 \Theta (\alpha (M + nk)\log{(M + nk)}) ，大约是 \Theta (M \log{M}) 的，应该能过所有的特殊性质 A 。

其实看到这个 c_j 和 a_{j,i} 有点像分组背包的样子，不过似乎不太可做。

也许是我太蒻了，有没有 dl 用这个方法过的）

考场上就写了这么多，估计也就 64pts 。

实际上只拿了 48pts ，应该是特殊性质写挂了）

T3 \color{#9D3DCF}\text{replace}

考场上先是写了一个用 string 暴力匹配的 \Theta (L_1 L_2) 暴力，准备拿前 5 个点，但是前前后后调了将近一个小时才调完。

这直接导致了后来只写了个哈希的优化，最后还写挂了）

然而前面的暴力过于暴力，大常数被卡到只过了前两个点，于是最后只拿了 10pts 。

正解其实是一个比较经典的 trick：把所有的 s1,s2 和 t1,t2 都穿插在一起，

每一组对应的字符之间用特殊字符 \texttt{\#} 隔开，然后跑一遍 AC 自动机多模匹配即可。

赛前看了一路的 AC 自动机结果没想到。。

T4 \color{#9D3DCF}\text{employ}

考场上一心写暴力，最后的时间只来得及写个全排列，所以只拿了 8pts 。

考完一出来就听到有 dalao 说最后一题是很水的容斥，直接当场裂开（

车上看到 zzk 在直播间里说这道题很可能是 ABC 或者 ARC 的原题，后来也在讨论区里翻到了，是 \color{#9D3DCF}\text{ARC207A Affinity for Artifacts}

已经不再对省一抱有不切实际的幻想。。

后来补题一直到两个多星期以后才补完，还特地为此写了一篇题解，不过没推上去。

Summary

今年的前两题可以算是贪心和基础算法掌握不熟练，这一点只能多刷题。

后两题的话其实用暴力数据结构也能做，但是如果写到过这些 trick 会更顺一些。

总的来说还是三点：