Travel「CSP 2025 游记」

denominator · 2025-11-01 21:02:53 · 生活·游记

这场考得就是史。

Day 1

开场看题：

T1：

• 其实第一眼是不会的。
• 1min 以内会做了，表现在读题上就是读下一题了。
• 不过写这玩意硬控我 30min。

T2：

• 一开始读错题了，写了很长一段代码。
• 读对了之后，写了个 \mathcal O(nk2^k) 的做法。考场上算错以为是 \sout{\mathcal O(n3^k)}。
• 大样例 ~1800ms，非常悬。
• 在 O2、快读的大力加持下，跑 ~800ms 才过大样例。
• 测了个极限数据，~4000ms，没辙了（我也不知道为什么这么慢）。
• 最后还以为要优化，索性扔了。
• 貌似这会已经 2h 了。

T3（第一次）：

• 当时以为只需要中间一段（包含所有 x_1,x_2 不同的位）相同就行了。
• 然后显然地，样例 3 寄了。
• 发现问题后觉得貌似不太好处理，下一个。

T4：

• 先写了个 \mathcal O(n^22^n) 的暴力。
• 然后是 AB 性质。
• 想了一会，好像这两个性质就是正解的两面，也就是非常接近 std 了，果断放弃吧！
• 于是就这样漏掉了 n=m 这个简单的点。

T3（第二次）：

• 好像可以转 ACAM，但是第一次想的时候时间复杂度是 \mathcal O(L_1|\Sigma|^2+L_2\log n)，非常的劣。
• 后期发现可以简单地优化为 \mathcal O(L_1|\Sigma|+L_2)。
• 还有 1.5h，时间绰绰有余，赶紧写吧！结果忘记 ACAM 的 fail 怎么建了。
• 结果发现暴力用 KMP 匹配有 50，还有 1h，时间绰绰有余，快去冲！
• 结果把样例 3 的第 102 问扒下来，答案 28，输出 25。
• 甚至写了暴力跑也是 28，更加确定是 KMP 的问题。
• 于是忘记了 |t_1|\neq|t_2| 是可能的。
• 于是干到了比赛结束。

咕分：100+[80,100]+[0,50]+[8,20]=[188,250]。

对不起，让大家见笑了。

这是那一天比赛后写的后记，当然赛后又加了一些：

• 已严肃学习 KMP 和 ACAM。
  • KMP 不是大家都先跳完 fail 再 ++ 的吗。
  • 我说先 ++ 再跳 fail。
  • 造出来的时候还感觉很对。
  • ACAM 大家的 fail 不都是一维的吗。
  • 我是二维的。
  • 赛后发现二维的数组是被改掉的出边数组。
• 成功成为全机房垫底。
  • 没人还能比我差吧。
  • 这么简单的场搞成这样也是没救了。

Day 5