CSPS2025 游记

· · 生活·游记

初赛

以下记 Day 1 为初赛比赛日。

Day -3~Day 0

考了四套初赛卷子，平均分 \le 80。

别笑，你来你也考不上 80。

但是好像要过不去初赛了/ll。

Day 1

中午海亮高级中学 \to 绍兴一中。

四十五分钟速通了，没有基础知识是好的，阅读二把高楼扔鸡蛋 k\le 2 拿出来放一遍交互版是何意味，完善二直接做有点难，看了做法就是容易的了。

睡了一会。

最后半小时翻阅卷子，发现我数排列数错了，重新数了一遍，然后完善二有个地方好像选错了，进行修改。

对答案应该是满分了。

Day ?

查分喜提 403\sim 404 分波动。查到的第一个 \le 100 的分数取满了上界，这是好的。

复赛

以下记 Day 1 为复赛比赛日。

比较慌，怕过不去 T2，原因【数据删除】。

只想看正赛的可以在右边选。

Day -25

暑假后第一次打四题模拟赛，感动了/kel。

奶龙信息学奥林匹克世界大战，100+79+52+0=231，rk 8。

T2 几乎整个机房都在想凸性，比较搞笑。

T3 是非多项式复杂度 counting，毅然决然去做 T3，但 T4 是唐唐平衡树维护置换环，送了不少分。

然后奶龙王就狙击成功了。

Day -22

神秘 T2 被赛后 hack 了，唉。 T3 太困难了，做不了一点。 ### Day -18 thomaswmy 搬的题目。 $100+80+100+25=305$，rk 2。 做 T2 两个小时，拼劲全力无法战胜，莫队匆匆跑路。 T3 是容易题，T4 是神秘构造。 如此成绩，如何 CSP。 ### Day -16 $100+58+0+100=258$，rk 6。 T2 挺板的，加两句话的事情我口胡了一个容斥再加点边容斥的 $20$ 倍常数的树剖 BIT。 T4 是哈集幂板子，比较唐。 鉴定为 1423。 ### Day -14 $10+100+100+60=270$，rk 12。 两道计数，放在两道签到 T2，T3。 T4 不难，但是我做法太诡异了调不了。 T1 是 meet in the middle 板子，但是写挂了没挂拍，于是寄。 ### Day -11 $100+100+90+10=300$，rk 4。 前三题基本都是送的，T3 随机卡常被卡掉 $10$ 分，加个快读就过了。 但是 T3 貌似都不是正解复杂度，如何呢？ ### Day -9 $100+100+100+30=330$，rk 3。 也是送了三题，T3 又是平衡树维护置换环。 T4 是巨大分讨 ds，两个等价的部分只来得及写一半，能过特殊性质，然后拼分拼挂了，如何呢？ ### Day -8 $100+45+0+0=145$，rk 13。 T2 是奇怪 greedy，成功假掉。 写了一整场 T4 调不出来。唉，菜是原罪。 ### Day -4 $80+100+100+0=280$，rk 4。 T1 log 太难写，写了个分块没过 $2\times 10^5$。 T3 是板板点分治+虚树+换根 dp，T4 是巨大困难推性质。 如何 CSP？ ### Day -3 $100+100+60+19=279$，rk 7。 前两题是送的，T3 是困难 counting，T4 是答辩。 小店解析：T3 的得分可看作 $60\sim 98$ 均匀分布。 ### Day -2 $70+100+100+60=330$，rk 2。 难度顺序，T3 是简单的，T2 是神秘猜性质，T1 是抽象计数，T4 是困难题。 四紫模拟赛，唉。 ### Day -1 打板子，敲了 kmp，manacher，tarjan，点分治，李超树，树哈希。 VP CF，被蓝题卡了。 ### Day 0 划水，ZJOI 迷宫是人做的？ 晚上六点海亮高级中学 $\to$ 全季未来科技城绿汀路酒店。 和 ricefruit 住在一起。 ### Day 1 上午随机看题，和 zzzcr 大战十五分钟黄题，勉强战胜。尝试调昨天写的某个题。 中午食用了盒饭。 下午进场，并未携带食物。 睡了一会，醒来时发现口袋并没有手机，这是好的。 读密码时成功没来得及打也没来得及记，读第二遍才打开。 开场看题发现 T1 应该不难，T2 没什么想法，T3 好像是串串，T4 是 counting。 花了 $6$ 分钟仔细读了一下 T1，T2，T4，发现不会 T2，T4。 想了 $5$ 分钟 T4，没什么想法，先去看 T1。 秒了，直接调整，敲了一会敲完了，$14$ 点 $47$ 过大样例。 看 T2，发现 $k\le 10$，想一会只会 $2^k(m+nk)\log m$。 快 $15$ 点时会了发现 $m$ 可以缩成 $n$，于是是 $2^k nk\alpha(n)$，感觉不能过。 几分钟发现可以一边搜一边缩边一边归并排序，是 $2^k(n+k)\alpha(n)$，进行写，准备写完上厕所。 $15$ 点 $12$ 过了大样例，感觉不太会被卡常。 仔细阅读了 T3 题面，发现离线并缩掉两端相同后每一类是查询 $s_1$ 是 $t_1$ 后缀且 $s_2$ 是 $t_2$ 前缀的数量（$s,t$ 意义有变）。 想了一会发现可以直接在两棵 trie 上做二维数点，算一下发现 $10^7\times 26$ 个 int 加上 $10^7$ 个 vector 总共 $4\times 10^5$ 个 pair 元素只比 1GB 多一点，不会 MLE。 复杂度 $O(L+(n+q)\log L)$。 因为怕被卡常，用了一个状压存哪些字符上有儿子。 准备调完上厕所。 写了一百万年，调了一百万年的 RE，发现是有个地方 `x&-x` 写成了 `x^-x`，比较搞笑。 调完 RE 后一遍过大样例了，$16$ 点 $39$ 过的。 思考 T4，感觉是方案数延后计算然后 dp 设一个 $f_{i,j,k}$，显然有两维状态 $i,j$ 是当前到了 $i$，前面毙掉了 $j$ 个人。 先假定 $s_i$ 为 $c_x\ge i$ 的数量，$t_i$ 为恰好 $i$ 的数量。 $k$ 本来我想设为前面被毙掉的 $c_i>j$ 的人数，发现不太好算后面的 $c_i>j$ 的人数。 想了一会发现应该设为前面面试过（被毙掉，被选上）的 $c_i>j$ 的人数，此时前面面试过的 $c_i\le j$ 的人数是 $i-k$，后面的 $c_i\le j$ 的人数是 $(n-s_{j+1})-(i-k)$。 然后考虑转移，若第 $i$ 天是好的，则 $f_{i-1,j,k}\to f_{i,j,k+1}$（$c_x>j$，不决定具体是谁），$f_{i-1,j,k}\times \binom{t_{j+1}}{l}\binom kll!((n-s_{j+1})-(i-1-k))$（$c_x\le j$，决定是谁，$c_x=j+1$ 的枚举前面用过的数量，进行选择，选择，匹配）。 否则差不多，只不过当 $c_x>j$ 时也会 $j$ 增加并枚举数量。 复杂度 $O(n^4)$，需要 for $i,j,k,l$。 最后答案是 $\sum\limits_{i=0}^{n-m}f_{n,i,s_{i+1}}s_{i+1}!$。 准备敲一下之后上厕所。 发现可以推之后就直接照着写，可以过第三个样例。 尝试把 $l$ 去掉，直接推发现要 NTT，感觉写不出来。 对着代码瞪，突然发现 for $j,l$ 总量是 $O(n)$ 的（$l\le t_{j+1}$），所以复杂度其实是 $O(n^3)$。 敲了一个滚动并把数组开大，开 O2 测最大样例 0.8s。 $17$ 点 $42$ 分过了全部大样例。 AK 了？真的吗？ 上了一下厕所（没上过），打了两把 tetris，下了会五子棋。 结束了。 ricefruit 表示他 $17$ 点不到切了四个题，进行拜谢。 出场发现 T3 查询串长可能不同，然后我忘记自己有没有判了，非常慌，感觉自己没判。 写了一下 T1，T4，luogu 上可以过。 upd：查分了，$100+100+100+100=400$，WC 显然是可以去了 T3 出题人，可以多 $100$ 个母亲！ ## 后记 我还年轻吗？ 我还年轻……吧。 从来到海亮高级中学算，正式学 OI 已经有两年，想到两年后我将成为高一选手，被更新的选手薄纱；再两年后就成为了高三学生，不知是成为 winner 还是成为败犬。 说是游记，却也是对近两个月对 CSP 努力的简略总结。 希望 zzzcr 学长与 fangzichang 学长进入省队，获得金牌。 我该在哪里停留？我问我自己。