专栏文章

CSPS2025 游记

jjiazhichen844
生活·游记参与者 102已保存评论 110

文章操作

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

当前评论
108 条
当前快照
1 份
快照标识符
@mhz4uxqr
此快照首次捕获于
2025/11/15 01:29
3 个月前
此快照最后确认于
2025/12/02 01:08
3 个月前
查看原文

初赛

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

Day -3~Day 0

考了四套初赛卷子，平均分 ≤80\le 80。
别笑，你来你也考不上 8080。
但是好像要过不去初赛了/ll。

Day 1

中午海亮高级中学 →\to 绍兴一中。
四十五分钟速通了，没有基础知识是好的，阅读二把高楼扔鸡蛋 k≤2k\le 2 拿出来放一遍交互版是何意味，完善二直接做有点难，看了做法就是容易的了。
睡了一会。
最后半小时翻阅卷子，发现我数排列数错了，重新数了一遍，然后完善二有个地方好像选错了，进行修改。
对答案应该是满分了。

Day ?

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

复赛

以下记 Day 1 为复赛比赛日。
比较慌，怕过不去 T2，原因【数据删除】。
只想看正赛的可以在右边选。

Day -25

暑假后第一次打四题模拟赛，感动了/kel。
奶龙信息学奥林匹克世界大战，100+79+52+0=231100+79+52+0=231，rk 8。
T2 几乎整个机房都在想凸性，比较搞笑。
T3 是非多项式复杂度 counting，毅然决然去做 T3，但 T4 是唐唐平衡树维护置换环，送了不少分。
然后奶龙王就狙击成功了。

Day -22

100+90+50+0=240100+90+50+0=240，rk 6。
神秘 T2 被赛后 hack 了，唉。
T3 太困难了，做不了一点。

Day -18

thomaswmy 搬的题目。
100+80+100+25=305100+80+100+25=305，rk 2。
做 T2 两个小时，拼劲全力无法战胜，莫队匆匆跑路。
T3 是容易题，T4 是神秘构造。
如此成绩，如何 CSP。

Day -16

100+58+0+100=258100+58+0+100=258，rk 6。
T2 挺板的，加两句话的事情我口胡了一个容斥再加点边容斥的 2020 倍常数的树剖 BIT。
T4 是哈集幂板子，比较唐。
鉴定为 1423。

Day -14

10+100+100+60=27010+100+100+60=270，rk 12。
两道计数，放在两道签到 T2，T3。
T4 不难，但是我做法太诡异了调不了。
T1 是 meet in the middle 板子，但是写挂了没挂拍，于是寄。

Day -11

100+100+90+10=300100+100+90+10=300，rk 4。
前三题基本都是送的，T3 随机卡常被卡掉 1010 分，加个快读就过了。
但是 T3 貌似都不是正解复杂度，如何呢？

Day -9

100+100+100+30=330100+100+100+30=330，rk 3。
也是送了三题，T3 又是平衡树维护置换环。
T4 是巨大分讨 ds，两个等价的部分只来得及写一半，能过特殊性质，然后拼分拼挂了，如何呢？

Day -8

100+45+0+0=145100+45+0+0=145，rk 13。
T2 是奇怪 greedy，成功假掉。
写了一整场 T4 调不出来。唉，菜是原罪。

Day -4

80+100+100+0=28080+100+100+0=280，rk 4。
T1 log 太难写，写了个分块没过 2×1052\times 10^5。
T3 是板板点分治+虚树+换根 dp，T4 是巨大困难推性质。
如何 CSP？

Day -3

100+100+60+19=279100+100+60+19=279，rk 7。
前两题是送的，T3 是困难 counting，T4 是答辩。
小店解析：T3 的得分可看作 60∼9860\sim 98 均匀分布。

Day -2

70+100+100+60=33070+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。
花了 66 分钟仔细读了一下 T1，T2，T4，发现不会 T2，T4。
想了 55 分钟 T4，没什么想法，先去看 T1。
秒了，直接调整，敲了一会敲完了，1414 点 4747 过大样例。
看 T2，发现 k≤10k\le 10，想一会只会 2k(m+nk)log⁡m2^k(m+nk)\log m。
快 1515 点时会了发现 mm 可以缩成 nn，于是是 2knkα(n)2^k nk\alpha(n)，感觉不能过。
几分钟发现可以一边搜一边缩边一边归并排序，是 2k(n+k)α(n)2^k(n+k)\alpha(n)，进行写，准备写完上厕所。
1515 点 1212 过了大样例，感觉不太会被卡常。
仔细阅读了 T3 题面，发现离线并缩掉两端相同后每一类是查询 s1s_1 是 t1t_1 后缀且 s2s_2 是 t2t_2 前缀的数量（s,ts,t 意义有变）。
想了一会发现可以直接在两棵 trie 上做二维数点，算一下发现 107×2610^7\times 26 个 int 加上 10710^7 个 vector 总共 4×1054\times 10^5 个 pair 元素只比 1GB 多一点，不会 MLE。
复杂度 O(L+(n+q)log⁡L)O(L+(n+q)\log L)。
因为怕被卡常，用了一个状压存哪些字符上有儿子。
准备调完上厕所。
写了一百万年，调了一百万年的 RE，发现是有个地方 x&-x 写成了 x^-x，比较搞笑。
调完 RE 后一遍过大样例了，1616 点 3939 过的。
思考 T4，感觉是方案数延后计算然后 dp 设一个 fi,j,kf_{i,j,k}，显然有两维状态 i,ji,j 是当前到了 ii，前面毙掉了 jj 个人。
先假定 sis_i 为 cx≥ic_x\ge i 的数量，tit_i 为恰好 ii 的数量。
kk 本来我想设为前面被毙掉的 ci>jc_i>j 的人数，发现不太好算后面的 ci>jc_i>j 的人数。
想了一会发现应该设为前面面试过（被毙掉，被选上）的 ci>jc_i>j 的人数，此时前面面试过的 ci≤jc_i\le j 的人数是 i−ki-k，后面的 ci≤jc_i\le j 的人数是 (n−sj+1)−(i−k)(n-s_{j+1})-(i-k)。
然后考虑转移，若第 ii 天是好的，则 fi−1,j,k→fi,j,k+1f_{i-1,j,k}\to f_{i,j,k+1}（cx>jc_x>j，不决定具体是谁），fi−1,j,k×(tj+1l)(kl)l!((n−sj+1)−(i−1−k))f_{i-1,j,k}\times \binom{t_{j+1}}{l}\binom kll!((n-s_{j+1})-(i-1-k))（cx≤jc_x\le j，决定是谁，cx=j+1c_x=j+1 的枚举前面用过的数量，进行选择，选择，匹配）。
否则差不多，只不过当 cx>jc_x>j 时也会 jj 增加并枚举数量。
复杂度 O(n4)O(n^4)，需要 for i,j,k,li,j,k,l。
最后答案是 ∑i=0n−mfn,i,si+1si+1!\sum\limits_{i=0}^{n-m}f_{n,i,s_{i+1}}s_{i+1}!。
准备敲一下之后上厕所。
发现可以推之后就直接照着写，可以过第三个样例。
尝试把 ll 去掉，直接推发现要 NTT，感觉写不出来。
对着代码瞪，突然发现 for j,lj,l 总量是 O(n)O(n) 的（l≤tj+1l\le t_{j+1}），所以复杂度其实是 O(n3)O(n^3)。
敲了一个滚动并把数组开大，开 O2 测最大样例 0.8s。
1717 点 4242 分过了全部大样例。
AK 了？真的吗？
上了一下厕所（没上过），打了两把 tetris，下了会五子棋。
结束了。
ricefruit 表示他 1717 点不到切了四个题，进行拜谢。
出场发现 T3 查询串长可能不同，然后我忘记自己有没有判了，非常慌，感觉自己没判。
写了一下 T1，T4，luogu 上可以过。
upd：查分了，100+100+100+100=400100+100+100+100=400，WC 显然是可以去了
T3 出题人，可以多 100100 个母亲！

后记

我还年轻吗？
我还年轻……吧。
从来到海亮高级中学算，正式学 OI 已经有两年，想到两年后我将成为高一选手，被更新的选手薄纱；再两年后就成为了高三学生，不知是成为 winner 还是成为败犬。
说是游记，却也是对近两个月对 CSP 努力的简略总结。
希望 zzzcr 学长与 fangzichang 学长进入省队，获得金牌。
我该在哪里停留？我问我自己。

评论

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

正在加载评论...