记一次 CSP 挂分

· · 生活·游记

Day -1

本来有一场模拟赛，但太紧张了，不想打。听说题目不错，口胡了前两道但不想写。晚上润回家了，严肃进行了一次女装，但并没有心情拍照。

Day 0

之前这么摆烂的状态不能再继续下去了。

为适应考场环境，我决定改用 NOI Linux 摆烂。几个月前把备用机的系统换成了 NOI Linux，并且装了一些常用软件，于是用备用机进行了水群和打隔膜。

比较舒服的是，似乎在这台电脑上运行 Minecraft: Java Edition 比之前装有 Windows 时流畅得多。比较不舒服的是，fcitx 输入法好难用，这对我水群造成了一定影响。那几天不想折腾电脑，懒得去装 Rime 或者搜狗。

Day 1 赛前

上午继续水群，下午去杭师大仓前校区，很快遇到了同学。考前报密码的时候很顺利解开了第一层压缩包，但以为第二层压缩包有另一个密码，遂错过第二次播报，在开考前一分钟才想到向监考人员求助。

Day 1 赛时

开考十分钟，尚未想出 T1 的解法，决定先跳题。很快会了 T2，但写挂了。开考三十分钟，决定先回过头看一下 T1，发现是简单题，很快写完了，回过头发现 T2 犯了一个很唐的错误，修完后通过了全部大样例。此时是开考一小时。

开始看 T3，马上注意到多模匹配，但 AC 自动机并不在考纲以内，然而并未想出可以不使用 AC 自动机的解法。很快有了两种思路：

  1. 取出差异部分做哈希，然后我不知道怎么匹配上其他部分。
  2. 将两个字符串相同位置的两个字符合并，映射到 [1,676]，直接跑 AC 自动机，但显然会炸空间，且无法保证包含完整的差异部分。

然而，接下来的几十分钟内，我始终没想到这两个东西组合起来就是一种可行的解法。期间开了一下 T4 但没有什么头绪。大概开考两小时的时候想到可以根据第一种思路建立多个 AC 自动机，同时由于差异模式已经匹配，可以将字符集从 676 压缩到 52。于是花费了大半个小时进行实现。

最后只剩下 T4，始终未能想出正解，遂在考试结束前五十分钟开始打暴力。实现了一个能拿前两档分的 O(2^nn^2) 状压 dp，再实现了一下 m=1 和 m=n 的特殊性质。

十分钟后考试结束。预期得分 100+100+100+36=336。

Day 1 赛后

发现 T3 没判 |t_1|\ne|t_2|，可能会挂分。

发现 T2 用的是 O(m\log m+2^kkn\log kn)，可能被卡到不低于 80 分，但随后发现数组开小了（场上过于紧张看成了 n=1000），这将导致直接挂到 48 分。

发现 T3 数组也开小了，由于需要多个而不是一个 AC 自动机，需要将数组开到 L_1+n 而不是 L_1。但随后发现 L_1 是 \sum|s_1|+|s_2| 而不是 \sum|s_1|，于是只需要 \frac{L_1}{2}+n，绰绰有余。

发现 T4 的 m=1 写的是假做法，但随后几天通过了全部民间数据的对应测试点。很容易 Hack 但有很大概率通过随机数据。

挂到 100+48+[0,100]+[24,36]=[172,284]，难受了好几天。

出分

感谢 T3 出题人没有卡 |t_1|\ne|t_2|，得 100 分。

感谢 T4 出题人没有想到能这样乱搞，得 36 分。

最终得分：100+48+100+36=284。

这个分数段内 T2 仅得 48 分是及其少见的。

随后几天内，民间排名和官方获奖名单陆续公布，全国排名六百出头，还有机会能去 NOIWC2026。但因为一些低级错误导致排名翻倍还不止，此后引以为戒。