CSP 2025 游记

WZwangchongming · 2025-09-29 20:40:25 · 生活·游记

Day -???

初赛日。

突然有点后悔没有去搞个 GESP，这样就可以睡懒觉了。

上午是 J。总算感觉比去年难。选择题简单速通一下，阅读程序不太想手模，看感觉排了俩不太可能的。完善程序简单看一看就选了。欸最后是个交互？欸这不是我们尊贵的 AT_arc070_d 吗？回忆了一下简单 30min 做完了。坐牢 1.5h。

下午是 S。这不比去年简单？选择题简单速通一下。阅读程序看了看，盲猜会有一些小屁孩去模拟 dfs。看懂意思之后直接自信选下。这代码越来越有 AI 味了。完善程序又考最短路？简单分层图？它写了个麻烦点的做法。第二题是什么玩意，这不是常识就可以选的吗？30min 做完了。

估分 J 100，S 80？

实际得分 J 100 \rightarrow < 90，S 80 \rightarrow 70 左右。我是挂分大王。

以下可能只记录一些印象比较深刻的比赛。

10.3 Day -???

洛谷大小月赛。

洛谷 10 月月赛 I &「SFMOI」Round II

先看 Div 2。T1 小卡一下，先去秒了 T2。回来发现自己糖丸了，秒了 T1。看 T3，随便分解一下质因数，然后上个二分套数论分块，复杂度对完了啊？遂 20min 过掉。看 T4，一眼了，纯种二分一下求完区间，然后对着左端点扫描线就是正确的。写写写，套个 BIT 就对完了，过的时候比赛刚开始 1h。

看榜，居然是 rk4？

再看 Div 1。把 T3 转换成了一个最短路状物，但是调试 1h 没有获得分数，遂写暴力。T4 一眼拿到了应该获得的 12 pts。T5 坐牢，摆。

看榜，222 pts，rk 27。

怎么 Div 2 T3、T4 都是蓝？

10.7 Day -???

洛谷 10 月月赛 II & FAOI-R8

速通了 T1、T2，T3 发现可以平衡树+桶维护一下，遂写。调试 3h Treap 无果，最后拼死拼上了 5+21 的可怜暴力分，226 rk 73 遗憾离场。

10.18 Day -???

洛谷 SCP 2025 模拟赛

T1 是简单二分。T2 就卡住了，发现了一些没有什么用的性质，而且不会任何一档暴力以上的分数。遂看 T3，发现：

定义 f_i 表示从 i 开始的列车可以到达的第一个站。可以发现 f_i 单增且 [f_i,n] 的所有站台均可从 i 到达。查询则是找一个包含 [x,y] 区间的列车的最小长度。答案为 \min\limits _{i=1}^x p_{\max(f_i,y)}-p_{i}。

拆一下：

• 对于所有 f_i\leq y 的 i，我们求 p_y-p_i 的最小值，我们找到最后一个 f_i\leq y 的 i 计算答案即可。
• 对于 f_i>y 的 i，我们求 p_{f_i}-p_i 的最小值。直接区间赋值。

随便抓一棵 SGT 维护，所以秒了 T3，然后局部变量定义太大无法输入虚空调试 1h。切完后看 T2、T4，坐牢 3h，再次拼上可怜的暴力 8+4，212 pts，rk 243 遗憾离场。

10.25 Day -???

起床的时候只有 1h 了，速通一下 MX CSP-J 模拟。

速通失败。死因：4 min 速通 Dijkstra 奇偶最短路手速太慢。

下午是 MX CSP-S 模拟。

开考。T1 不会，T2 不会，倒闭了。

看 T3，发现是非常有意思的群论。写个搜看看生成子集的大小，只有 156！那么直接暴力枚举一下每个可能生成的集合，把其中的边找出来，求连通性然后查询每个询问是否连通即可，对于每个询问找出取最小可以连通的集合。啪的一下 1h 通过了大样例。诶？S 考群论何意味？

回来看 T1，发现了一些规律，写写写过了。我直接 chk 到 100，后来发现只要 91 就可以了？

T2 倒闭，观察了一下没发现什么有用的性质，遂尝试换根 dp。大战 2h，最后样例只能过一个特殊性质。

现在只剩 30min，被迫在 T2 正解和 T4 暴力之间做出抉择。我选择 T4 暴力！拆完经典贡献迅速 rush 掉 O(n^2) 的暴力获得了 25pts。经典总司令环节，我相信我的 T2 假做法可以通过特殊性质，在仅剩 2min 放弃思考的时候提交了假做法。

看着倒计时的 1min，我算了一下，似乎是 100+40+100+25=265 的尴尬分数。出榜给我吓了一跳，T2 假做法把暴力和最大点多艹了七个？

100+75+100+25=300，rk 31。感谢 T2 不捆测和出题人的数据。也祝贺我再次场切紫。

晚上是核桃 S 模拟，同学速通了 T1、T2，我发现 T3 map 乱维护一下就可以过！我发现 T4 找桥缩点 dfs 一下就可以过！

注意力太惊人了，100+100+100+100=400，rk 1。

可能算是 CSP-S 正赛前打的最好的两场模拟赛？我 T2 似乎一直都很难获得很高的分数？发现我似乎是 T3 战神？

Day -1 10.31

逃离学校。晚上回家随机看板子，倍增 LCA 调了 3 发，Treap 调了 2 发，CDQ 调了 eps 发……当我看到图论算法时，我认为应该不会考最短路和 MST 的吧？

摆，加训原神。

Day 0 11.1

十点多抵达杭州，钟点房爆睡 0min。两点进场。依旧坐牢。场内咋一堆老熟人？密码是人杰地灵（）。

开 T1，很好，很好，不超过 \frac{n}{2} 个。一眼反悔贪心，按最大值减去次大值升序丢进堆里，超过 \frac{n}{2} 就减到满足条件，然后反着减掉贡献。花 1min 写了写缺省源，迅速开码，在 25min 左右通过了这个题的所有大样例。

T2 看起来就很 MST 的样子（伏笔回收），我考前就没复习图论！。硬着头皮再读了读题面，思考了 1h 的分层图上 MST 再反着减贡献的做法，写完发现假了。此时我发现这个假做法的代码可以通过特殊性质，仔细想了一想确实如此。便想写个暴力去看后面的题：状压 k，每次做 MST 再统计答案。写了一发，发现可以只全局排一次序，单次 Kruskal 的时候就是 O(点数) 的了。发现大样例全过了？最大的大样例 0.8s？仔细算了一下复杂度，发现是 O(nk \log nk+2^k(n+k)) 的，才 2e8 左右？此时 2h 左右，体感这个题挺反直觉的。

T3 一眼先字符串哈希，把两个串的 \text{lcp} 和 \text{lcs} 拆掉。然后可以按照这个东西分类。然后无脑建出 Trie，或者在失配树上 dp 一下就对完了？注意这里的 Trie 的儿子是一个形如随机叉的结构，所以上 map 搞一下。写了 30min，发现样例全错了。

此时我觉得这破玩意儿又臭又长不好调，滚去想了一下别的做法：假设 t_i = 二元组 (t_{1, i}, t_{2, i})，s_{j, i} = (s_{j, 1, i}, s_{j, 2, i})，那么 t 能在某个子串进行替换，当且仅当该子串包含了所有 t_1 \neq t_2 的位置，并且该子串等于某个 s_j。那么现在相当于做给定字符串 t 和一段区间 [l, r]，求每个模式串作为 t 的子串并且包含 [l, r]，一共出现几次的问题。

那么接下来就是无脑做法，建出 ACAM：

• 对于 r 的限制，那么只在 [r, |t|] 处进行统计即可。
• 对于 l 的限制，只要减去左端点在 l + 1 以右的答案即可，相当于从 t_{l+1} 开始重新跑一遍自动机。

赛后发现，这两个做法都是正确的。但是我赛前只写了一次 ACAM，怕我自己写错，遂返回调试 Trie 求交的做法。调试 1h 过了大样例，但是最大的样例跑了 3s。遂卡常，在经历若干卡常后，最大的样例跑进了 2s。因为理论复杂度是对的，所以我就当 CCF 评测机会放我过的吧。

只剩 30min 了，我看了一眼 T4 性质，迅速秒了 0 和 n!，全力拼暴力。可能是紧张的时候犯糖，我的暴力到 6:28 的时候才写完。测都没有测，整理检查了文件就上交了。

得分希望是 100+100+100+12=312 吧。

Day 1 11.2

发现讨论度很高的 |t_1| \neq |t_2| 我似乎也没判，现在 T3 又增添了一分神秘。

Day ??? 11.5

卡 bug 进了系统。？？？？？？？？？