专栏文章

记一次 CSP 挂分

MMrkn_chenyx12
生活·游记参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mi3z2rad
此快照首次捕获于
2025/11/18 10:46
3 个月前
此快照最后确认于
2025/12/01 21:15
3 个月前
查看原文

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][1,676]，直接跑 AC 自动机，但显然会炸空间，且无法保证包含完整的差异部分。
然而，接下来的几十分钟内，我始终没想到这两个东西组合起来就是一种可行的解法。期间开了一下 T4 但没有什么头绪。大概开考两小时的时候想到可以根据第一种思路建立多个 AC 自动机，同时由于差异模式已经匹配，可以将字符集从 676676 压缩到 5252。于是花费了大半个小时进行实现。
最后只剩下 T4，始终未能想出正解，遂在考试结束前五十分钟开始打暴力。实现了一个能拿前两档分的 O(2nn2)O(2^nn^2) 状压 dp，再实现了一下 m=1m=1 和 m=nm=n 的特殊性质。
十分钟后考试结束。预期得分 100+100+100+36=336100+100+100+36=336。

Day 1 赛后

发现 T3 没判 ∣t1∣≠∣t2∣|t_1|\ne|t_2|，可能会挂分。
发现 T2 用的是 O(mlog⁡m+2kknlog⁡kn)O(m\log m+2^kkn\log kn)，可能被卡到不低于 8080 分，但随后发现数组开小了（场上过于紧张看成了 n=1000n=1000），这将导致直接挂到 4848 分。
发现 T3 数组也开小了，由于需要多个而不是一个 AC 自动机，需要将数组开到 L1+nL_1+n 而不是 L1L_1。但随后发现 L1L_1 是 ∑∣s1∣+∣s2∣\sum|s_1|+|s_2| 而不是 ∑∣s1∣\sum|s_1|，于是只需要 L12+n\frac{L_1}{2}+n，绰绰有余。
发现 T4 的 m=1m=1 写的是假做法，但随后几天通过了全部民间数据的对应测试点。很容易 Hack 但有很大概率通过随机数据。
挂到 100+48+[0,100]+[24,36]=[172,284]100+48+[0,100]+[24,36]=[172,284]，难受了好几天。

出分

感谢 T3 出题人没有卡 ∣t1∣≠∣t2∣|t_1|\ne|t_2|，得 100100 分。
感谢 T4 出题人没有想到能这样乱搞，得 3636 分。
最终得分：100+48+100+36=284100+48+100+36=284。
这个分数段内 T2 仅得 4848 分是及其少见的。
随后几天内，民间排名和官方获奖名单陆续公布，全国排名六百出头，还有机会能去 NOIWC2026。但因为一些低级错误导致排名翻倍还不止，此后引以为戒。

评论

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

正在加载评论...