2025-CSP-S 游记

· · 生活·游记

Day -1

CSP 前最后的模拟赛，豪赤，拼尽全力 AK 了。

Day 0

CSP 前一天，本来上午想做题的，但是由于偶遇垃圾题，而且大家都开摆了，所以就做了一道题。下午看大家都走了就提前翘课回家了，摆了一个下午。

这是我第一次 CSP 不用参加 J 组，所以不用定酒店，只要第二天上午出发去就行了，所以也挺轻松的。睡的还行。

Day 1

上午

9 点左右起来的，随便吃了一点早饭，没什么精神，可能是因为平时都穿短袖，今天穿了一件比较厚的长袖，太热了，想睡觉。车程挺远的，要两个半小时，中途睡了一觉。

这时候才开始有点紧张，之前都因为平常做的是联赛模拟，所以潜意识里感觉 CSP 肯定会出的很简单，没怎么多想。快要上战场了，才仔细一想历年 CSP 也没多简单，去年自己也没考多好；况且 CSP 决定了很多比赛的参赛资格，还是很重要的。于是开始紧张起来了。

到了杭州还很早，准备在杭师大旁边随便吃点中饭，逛着逛着偶遇 mango，就顺便进了那家店。听说他在找其他同学的酒店，想和他们汇合，因为他们是提早一天来的，昨天晚饭都是在杭州吃的。后来他们还一起在酒店下了会军棋，羡慕。

那家店还不错，是吃东北烤串之类的，有一个样子和味道都很像啤酒的饮料，但是是无酒精的，喝起来有点别致。其他的话，肉挺多的，吃的很畅快，可惜我早饭吃的晚，没什么胃口。

下午

准备去杭师大里面了，一开始特意找了离考场有点距离的位置静静休息了一会，才和学校同学们汇合。因为是 CSP 所以不是同一行动的。去了这么多次杭师大，第一次考场在二楼，所以进楼就和他们分开了，只看到了 ljd 和我一个考场。看来不是按初赛成绩排序的。

进了考场才发现自己只带了一瓶水，但是考场又不通风，我还穿了很热的长袖，奇热无比，头昏昏的。本来想趁考试还没开始出去灌一瓶水的，但是由于不知道在哪里就放弃了，只能硬着头皮上了，真渴就随机应变吧。或许就是渴而且热的原因，导致我后来决策有点烧坏脑子了似的。

考前十分钟发解压密码，这次竟然不是分两批解压的。但是由于监考人员报最后一个 “%” 时根本听不见，再加上极为幽默的两层加密一个密码，导致我开考后才意识到早就可以看题了，哭哭。

发现系统版本还是很老，只能用 chrome 打开了 pdf。一打开，就是熟悉的格式，最近模拟考大家 pdf 都是这个格式，有种他乡遇故知的感觉。一看，四个一秒题，有点奇怪，但是没事，听说这次评测机很快，开一秒也合理。

开 T1，反复阅读了几遍，确认一下直接贪心是对的，就是直接先贪心然后反悔一些即可，就先往后看了。

开 T2，一张连通图，有 k 个额外点，看起来像最小斯坦纳树？求联通 n 个点的最小代价，果然是啊，难不成 CSP 放个最小斯坦纳树板子？记得这是没有 polylog 做法的，看看数据范围？k\le 10，和板子反过来了，n\le 10^4，那直接枚举取的集合不就好了吗。区区一个亿的计算量，应该可以过吧？但是 m 比较大，这没有关系，取最小生成树就行了。唉，简单题，往后看。

看一眼时间，才过了 12 分钟。开 T3，替换一个串，求方案数，多组查询。再看看，原来是只能操作一次，那只要把每对字符串找出本质有效的子段就行了，要求本质替换子段相同，直接哈希判一下。然后呢，好像类似于找有多少给定子串，难道是 acam？仔细一想，不对，好像是左边是后缀，右边是前缀，直接左右插进 trie 里做，好像带个 log，看看数据范围。n\le 2\times 10^5,L\le 5\times 10^6，一秒能过吗？不对，我的 log 可以在 n 上，所以没关系。

但是这个 L 还是会影响空间复杂度，因为是 26L，一测，495 MB，限制 512 MB 有点危险啊，总不会要用缩二度点之类的阴间技巧吧。再看看限制呢，原来是 2G 的空间限制，那肯定能过了。一个树状数组就解决的事，没什么难的。

过了 20 分钟了，开 T4，距离脑内 AK 只有一步之遥了，好激动。还有这么多时间，肯定能做出来吧。看看，这张卷子题目描述都挺奇怪的，需要仔细才能看懂。原来是相当于有一个变量 x，每次要么 x\gets x+1，要么 x\gets x+[x\ge c_i]，最后的限制可以转化为 x\le n-m，这个转化兼具了最后的条件和中间的转移，真是太优美了。

计数先看判定，但是判定似乎没什么可以深挖的。要排列计数啊，根据某位机房大佬的经验，排列计数，要么是连续段之类的，要么是有某种特殊结构，比如 unr 的那个，看看呗。先看连续段计数，这个 s_i 比较碍眼，先考虑 s_i=1 的特殊性质，能不能从小到大或者从大到小插入？感觉有点困难，没什么头绪。特殊结构呢，每次 c_i 放弃后，后面 \le c_i+1 的都会放弃，这好像也没什么用。总不能不是 dp 吧，但这看起来也很难直接计数。

似乎陷入死局了，我猛然想起来去年其他人的教训：留了很多时间给 T4 却徒劳无功，有些甚至不如暴力分。我得冷静下来，但是仔细一想，我现在才过了 30 分钟，还有的是时间，还是先继续想正解吧，相信下午一定和上午一样偏简单。但是没有水喝的困境和无比闷热的环境使我头痛，只能强行冷静下来，继续思考。如果开考后过了一个小时还想不出来，再先去打前面题目的代码，现在还不用急，我想。

看来问题还是在于排列计数吗，这个 x 的限制是关键，不妨先想想如果 x 的轨迹确定了怎么做，只有 s_i=1 的地方会变成 0，这与特殊性质 B 不谋而合。这样就变成了要求一些位置 \le x，一些位置 >x，一些位置无限制，这个 >x 看起来很碍眼，先容斥一下，这样就只有 \le x 和无限制了。这是一个经典问题，只要把第一个限制排序，就可以直接取了，剩下就是一个阶乘。但是这个复杂度连特殊性质都过不了。

考虑算贡献？但是这个与原集合和容斥后的集合都有关系，比较麻烦。但是这个简洁的式子，或许可以考虑直接 O(n^3) dp？欸，这个 x 具有单调性，也就我们只要从前往后一个一个取就行了，要记录什么呢？x，以及选的个数，这样就可以直接计算 \le x 的贡献了，但是还有一些无限制，此时这个选的个数这一维恰好可以确定剩余的数的个数，从而进行计算。这样就可以解决内层的容斥了。

但是还有外面一层枚举 x 的轨迹，这看起来不难解决，因为此时 x 的值这一维恰好可以判定最后的限制，似乎就差不多做完了？别激动，最后再整理一下，我列了一个详细的转移表格，反复确认了一下，还是不放心。反正这个写起来很短，写一下确认一下正确性吧。反正现在才过了 45 分钟，浪费了也无妨。

此时的我不知道，这 45 分钟，就是我这场考试全部的有效思考时间了。T4 很快就写完了，没过样例，调了调，过了，再一测，通过了所有大样例，我心里的一块石头落下了，虽然大样例弱，但计数题总不太可能挂分吧，除非数组越界之类的，似乎也不太会有。不管了，先把前三题写完，把满分收入囊中吧。

反正还有很多时间，我就特意写得很细致。写 T1，很快就写完了，应该没什么问题。写 T2，写的也不是很慢，但不知道为什么本地跑了 5s 左右，测来测去并查集都跑了 3s 多，怎么卡常都没什么区别，想着反正这次 CCF 机子出奇得快就先不管了。

此时已经只剩两个小时了，我才发现不对劲，这个 T3 似乎其实并不好写，时间有点危险了，但也只好硬着头皮加速写了，两棵字典树似乎可能开不下，后来改成了压成一棵，又怕 vector 开太多很危险，就用了链式前向星。总之花了不少时间，才通过了大样例，但还是怕数组 n,L 哪里开反了，因为本地测不出来。造了一组极限数据，跑挺快。我一边祈祷着 T3 不要挂细节，一边开始了检查。

反复测试了文件输入输出和大样例，一遍又一遍的检查着。我发现问题主要在 T2 和 T3 上了，T2 时间很危险，T3 正确性很危险。T3 没办法，只能多瞪一会儿。T2 呢，虽然做法已经理论上能过，但有没有优化的空间？我有想没想地想着，一方面做法已经理论能过，另一方面我当时也不觉得有更优的做法了，已经吃起了巧克力。

突然，在考试还剩 30 分钟时，我想到了一个 O(n2^k\alpha(n+k)) 的做法，但是时间似乎不够，只能尽力写了吗，我最后测好其他题的数据，就用剩下全部时间冲 T2 了。只要一个 dfs，一个归并排序，一个最小生成树，似乎还挺复杂的，不管了，无论是否写完，都先尽量写吧，反正也没事干了。

我拼了命地写着，还是差一步调完最后一步，现在想来似乎是只差没加 c_i 的问题了。但很可惜，时间不够就是不够，谁叫我不早点去想 T2 呢，不过是自作自受罢了。考试结束了，怀着对两道题的忐忑，我走出了考场。

赛时估分：100+[80-100]+[?-100]+100=380-400(-?)

晚上

出考场又遇到了 ljd。当时刚考完，加上室内闷热环境的烘烤，脑子昏昏的，加上人太多了，等到我想到袋子和衣服都没带出来已经晚了。我怀着对 T2 的强烈不安，反复倾诉着 T2 没调出来的痛苦。

似乎 ljd 后三道没做出来一道，这张卷子这么难么？考场外，大家都说着这场比去年难之类的话，“去年 T2 好歹会做，今年除了 T1 一道都不会”。仔细想来，今年平均难度确实挺高的，从 T2 开始就很容易挂分了。只是最难的题思维难度不高，导致我一开始对这张卷子的难度有了一些错误认知罢了。

熟悉的考场，熟悉的学校，熟悉的大门，来杭师大考了好几次的我们，早已熟悉了这条出考场的路，走出学校，意味着今年的 CSP 确实已经结束了。如墨一般的黑夜，确实与我当时心境不明地相合：一年的 CSP 已经结束了，而我的心却没有做好结束的准备，还是担心着 T2，T3 乃至 T1，T4 是否会挂分之类其实已无需担心的小事，正如夜晚是为我们这些还没有做好准备迎接下一天的人而出现的。

后来问了好多人，虽然有 T2 写更优的那个做法的，但大部分人都写的是我那个做法，但是大家似乎都跑得挺快，只有我本地很慢，不知道为什么，难道是我复杂度写假了，其实是 O(m2^k) 之类的？不得而知了。

T3 似乎很多人因为一些边界情况挂分了，我不是很确定自己有没有挂，有点担心。T4 似乎没有那么简单，还是有很多有水平的选手没做出来的，比如 mango 说他没调完，但我想着我做法也挺好写的，怎么会没调完呢？后来看了一眼洛谷题解，一时间没看到一个做法和我一样的，难道我做法其实假了，只是因为大样例都有特殊性质才侥幸过的？不过我也不敢去复现一遍测试正确性，还是等到正式公示吧。

晚饭在杭州吃的，也是以肉为主，其实挺好吃的，肉也很足，就是刚考完，心情有点低落，吃不太下。

回到家已经十点多了，路上太紧张睡不着，但是身体又因为考场环境以及过度紧张等原因极为疲惫，就在这种别扭的状态中，我结束了这一波三折的一天。

P.S.

T2 同机房有同学和我一个复杂度 T 了，我交了一下洛谷其实挺快的，但下回还是要注意这种情况，先想一个能想到的最优的算法。拿到公示代码很快就把 O(n2^k) 调出来了。

T3 很多人没判边界之类的，我似乎没有这个问题，反正最后正式数据大家都过了，应该是因为编译选项或者数据防水之类的神奇原因。

T4 不知道为什么大家都没做出来，感觉主要还是因为我那个做法刚好比较方便。

实际分数：100+100+100+100=400

初赛也是 100 分，初中最后一场正式赛也结束了，还是比较满意的。

其实首尾呼应了。