专栏文章

CSP-S 2025 游记

llzm0107
生活·游记参与者 13已保存评论 13

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
13 条
当前快照
1 份
快照标识符
@minezl37
此快照首次捕获于
2025/12/02 01:19
3 个月前
此快照最后确认于
2025/12/02 01:19
3 个月前
查看原文

Day ≤\le -1

模拟赛爆爆爆！

Day 0 (10.31)

试机，但没有机。
已完成今日「学长能不能给我签名？五块还是五百块」大学习。

Day 1

哎怎么七点半就醒了。
上午复习了一些板子，包括但不限于 FWT、点分治、割点，以及 SAM。感觉都不像会考的。
中午睡了半个小时。
去考点！！！
好像到考点到得比较早，于是开始水群，得知评测机 CPU 更新为 U9 285K。
进考场！！！
监考老师要求阅读电脑桌面上的一个可能是须知的 Word 文档，经仔细阅读后发现第二页中 NOI Linux 虚拟机相关内容中有“应提供虚拟机密码”类似文本。但显然要求选手提供密码并没有道理，合理猜测是下发前忘记将这里替换为密码了。
开考！！！
打开虚拟机，发现直接进入了桌面，并不需要密码。
开 A，∼20\sim 20 min 写完，经过一顿 ulimit 与 -fsanitize=address,undefined 的测样例和对拍后时间成功来到 ∼40\sim 40 min。
看 B，感觉一秒时限是很困难的，糊出 O(nklog⁡k⋅2k)O(nk\log k \cdot 2^k) 做法并认为太过逆天，思考了几分钟没动电脑后发现虚拟机自！己！锁！屏！了！
发现自己并不持有虚拟机密码的相关知识，尝试 cqbz 与 noi 未果，遂向监考老师求助。监考老师尚未走到就已看到屏幕，便说：“哦密码 123456”随后转向继续行走，全程均速。
继续思考 B，发现可以将所有 (k+1)n−1(k+1)n - 1 条边的边权离散化，随后在 2k2^k 枚举中每次只需要进行一次计数排序，时间降为 O(nk2k)O(nk2^k)，开写。
写完测完发现大样例的 n=103n = 10^3，于是自己造了一组 n=104n = 10^4 的数据，发现运行秒数 >1> 1。稍微卡两下卡到了 ∼0.7\sim 0.7。
此时感觉这场已经不会特别炸了，看完 C 根据参加模拟赛的经验想要开拼部分分时反应过来这是 CSP-S 不是 CSP-S 模拟赛。
发现一个替换合法的充要条件：
  • [l′,r′][l', r'] 覆盖了 t1t_1 与 t2t_2 的第一个不同位置 ll 与最后一个不同位置 rr。
  • s1s_1 与 t1[l′,r′]t_1[l', r'] 相同，s2s_2 与 t2[l′,r′]t_2[l', r'] 相同。
认为第二个条件可以通过将字符集平方后合并 s1,s2s_1, s_2 与 t1,t2t_1, t_2 变为“s=t[l′,r′]s = t[l', r']”。然后可以对所有 ss 建 AC 自动机。按照 tt 在 AC 自动机上转移，当第 i≥ri \ge r 个字符转移完后计算 r′=ir' = i 的 [l′,r′][l', r'] 对答案的贡献，需要对于 AC 自动机上，根到某结点的路径上，满足 dep≥i−l+1\mathrm{dep} \ge i - l + 1 的结点的点权求和。这个显然是做个前缀和后倍增找到最后一个 dep<i−l+1\mathrm{dep} < i - l + 1 的路径上的结点就可以做了。
感觉很好，但是 L1≤5×106L_1 \le 5 \times 10^6 完全无法接受 Σ=676\Sigma = 676 啊！
我们发现不用扩字符集，可以直接将 s1s_1 和 s2s_2 中的字符交替插入合并为 ss，将 t1t_1 和 t2t_2 中的字符交替插入合并为 tt。此时上面的 AC 自动机做法可以照搬。复杂度 O(L1(Σ+log⁡L1)+L2log⁡L1)O(L_1 (\Sigma + \log L_1) + L_2 \log L_1)，开写！！！
欸 AC 自动机怎么写的来着，这下回收伏笔了。
追忆写法并成功写完了 AC 自动机，在 -fsanitize=address,undefined 与 -D_GLIBCXX_DEBUG 的庇佑下发现了样例中的 ∣t1∣≠∣t2∣|t_1| \ne |t_2|，大样例 ∼0.4\sim 0.4 s。
此时还有 ∼80\sim 80 min，开 D，一开始看错题认为每个人判的是最近的未被录取的连续段。认为可以拿 3232 分。
打完 n≤10n \le 10 发现样例二跑出来完全不对，回去看看题面发现读错了。
重新想了一下发现可以拿 2424 分。
写完差不多就可以开始检查了，备份代码后 ulimit 测一遍，开 sanitizers 再测一遍。
结束啦！！！
出考场与【a】交流了情况，得知 D 与【c】前几天才讲的一道题差不多，但我当时被拉到下面机房做心理测评了？？？
得知【a】【b】C 题写的是 O(nlog⁡不知道什么东西)O(n \log \text{不知道什么东西}) 的二维偏序，且大样例不是极限数据，且【a】的的大样例跑了 ∼0.1\sim 0.1 s 后自造数据仍然跑了 >1>1 s，十分绝望。
回去后才想起来还有个 O(L1Σ)O(L_1\Sigma)，上 QQ 询问【a】他的 C 做法是否有这项，得到肯定回答。
我还以为我的 C 要慢 >20>20 倍呢（划掉）。
墓前估分不高于 324324。
感觉这个 D 完全是来破坏我的赛后心态的，明明打得没什么大问题却还是有点难过。
目前想法是不想在乎 CSP-S 分数了，反正结果只有“上 WC 线”“上 NOIP 线”和“爆完了”三种。

Day 5

哎怎么就 Day 5 了？
score≤324∧score≥324\mathrm{score} \le 324 \land \mathrm{score} \ge 324 了。
有 WC 去吗？

评论

共 13 条评论，欢迎与作者交流。

正在加载评论...