CSP-S 2025 游记

TB__QGSS__423 · 2025-10-03 14:12:58 · 生活·游记

10.1

上网课，被倍增和CDQ分治薄纱，听不懂

晚上补作业，和 @gcx12012 大佬组队 duel，100分险胜。

10.2

模拟赛

绿绿蓝紫，不想评价，分数没有大佬的初赛高/ll

10.3

数据结构专课

复习了并查集，树状数组，线段树，trie树等基本的。但出去过同学生日，没写题单。

晚上CF，A 的结论一眼，B 以为是大分讨，遂跳去做 C。写了一发，TLE了。又滚回去看 B，怒调 2 小时未果，摆了

赛后发现 B 其实代码很短，bbwzt

10.4

早上先补昨天的题，写了两绿一黄。

下午图论课，全紫黑阵容，摆摆摆。

gcx 和 onlycanzzzz 还去打了台，xm会打台。

晚上打 AT，A 和 B 直接秒了，C 是有点创新的题，但我貌似做麻烦了，用的线段树，导致过的有点慢。D 是 saber 找规律题，中间忘了，后面忘了，反正上分了。

写一写图论作业，顺利 A 了几道 Kruskal 重构树的题，一蓝一紫。

10.5

怎么就 10.5 了？？？

今日网课 belike：

一天又很快过去。

10.6

今天 0:35 的阴间 CF 场，运气还不错，AB 简单题，最后切了 C ，上了分。

模拟赛摆了，只打了 T2 的 50 分暴力

绿蓝紫紫，不嘻嘻。

唉，我怎如此颓废。

唉，怎么还有 25 天就 CSP 了。

10.12

从学校回来，刚月考完，摆

10.18

月考还不错，下午把 NOIP2024 第一题写了。

不打 AT CF 了，摆了。

10.25

MX 的模拟赛，黄蓝紫紫，只会 105 ，糖糖的。

寄希望于下周的自己。

11.1 正赛

10:30

早上起床，开始打板子。

[x] LCA
[x] Kruskal
[x] Dijkstra
[x] SPFA
[x] Floyd
[x] 线段树
[x] 字符哈希
[ ] Trie
[ ] kmp
[ ] 所有DP

于是你显然注意到，关于 DP 和字符串的我都没怎么复习，大部分集中在图论（埋下伏笔）

1:30

出门，和 @Onlycanzzzz 约了面积，路上还算通畅。

2:00

抵达，进校门前看见 xzk 大佬，吸收RP。

在机房门口遇见 Onlycanzzzz，给了我一根巧克力棒，光速炫完。看名单得知 cwm 大神也在同一机房，吸收RP。

今年进考场还要签名，绷。

光速调好环境，编译没问题（？？？

2:30

开考

先扫一眼题目，T1疑似 DP 或贪心，T2图论，T3字符串，T4计数。

他妈的为什么我赛前没复习 DP 和字符串！？

好吧骗你的，复习了也做不出来。

于是来看T1，每个成员分别分配给3个俱乐部，使每个俱乐部成员不超过 \frac{n}{2} 且满意度最大。真的很像背包，但我 DP 依托，跳去看 T2。

首先 T2 k=0 时的代码是简单的，直接跑最小生成树即可，发现有 16 分，在 T1 和 T2 间决定先把 T1 的 O(3^n) 暴力写了。

此时最勾八的地方来了，就在我准备编译运行时，这个 dev-c++ 突然坏了，点运行毫无反应。我瞬间汗流浃背，压力爆炸了。在经过包括修改编译器选项，退出重开，无能狂怒后，彻底认输，举手叫老师重装了。

我坐在一旁的椅子上，开始追忆，汗珠不停冒下，此时已过去 1 小时，正常来说我应该已经切了 T1，冲刺 T2 了，但现实却是 0 分，且有可能换机子，直接 return 0。给我心态搞炸了，那几分钟我想了很多，我感觉我对不起自己，对不起老师，对不起朋友，~~对不起全世界~~。准备了一个学期的 CSP 就这么输了吗？我问我自己。

好在还是修好了，以飞快手速打完暴力，去看 T3T4 的部分分，发现 T3 总司令，T4 有 24 分，遂打完。

然后发现 T2 有 O(2^km + m\log{m}) 的猎奇做法可写，顺利通过所有样例，不过有一两个超时，本来也没指望能 AC，有分就行。

此时还有 2.5 个小时，开始想 T1 的 DP，若定义 f_{i,j,k} 为分配了 i 个成员，1号社团有 j 人，2号社团有 k 人，3号社团有 i - j - k 人时的最大满意度。转移有

:::align{center}

f_{i,j,k} = \max(f_{i-1,j-1,k}+ a_{i,1},f_{i-1,j,k-1}+ a_{i,2},f_{i-1,j,k}+ a_{i,3})

:::

前提是转移是合法的，否则就不转，复杂度是 O(n^3)，然后再加个 A 性质。测大样例有一个挂了，但我找不出来，再加上时间所剩无几，只得放弃，听天由命了。

预期得分：[5,65]+[16,64]+[?]+[24,24]=[45+?,153+?]

我求你了CCF，别挂分别挂分别挂分别挂分别挂分别挂分别挂分别挂分，没挂分我每天赞颂 dzd。

等后面代码和成绩发了，会update，别挂成小丑就行。

upd

25+56+0+12=93，彻底输了。