Contradictory Sentimental Paradox | CSP2025 游记

· · 生活·游记

初赛前

参与了 SCP 2025 第一轮（初赛 S 组）模拟的命题（阅读 1 和阅读 3），难度得到了大家的一致认可。去年自己出的 2024 矩阵群非专业级别小潜可爱能力认证第一轮 （SCP-S1）提高级 C++ 语言试题 恰好也只有选择题是认真出了，算是补完计划。（补全程序：？？？）

初赛

选择题最后一题想了一会儿。之后做完检查的时候突然意识到咋全都没写数据范围？？？阅一 n<0 怎么办？阅二溢出了怎么办？阅三 p_i<0 怎么办？哎呀摆烂了好像只有阅一这么解释是自洽的，虽然 CCF 大概不会考虑这点吧但还总是想写上，不管了啊。出俩交互题也是神人了，复赛不会有交互吧。

预期的 \boxed{98.5} 的捏。后来 pmd 告诉我前面那个鹰蛋问题和后面那生产线本质相同的，不能掉落超过 k 次等价于不能退回超过 k 次，都是 0/1 的返回，这么深刻啊，以前一直不知道鹰蛋问题的组合解释。

复赛前

被 Aya 要求看了 SCP-S 的 T4，一开始想假了不过假做法和正解差不多（好像写起来还烦一点），修修补补就对了。据说个人差挺大的/fendou

萌熊模拟 T3 是题啊？？？？？

AtCoder 终于 5Dan 了。

严肃学习斜二倍增。

赛前随缘看了看 Manacher，也就只打了个最大流板子。

为什么会这么紧张的说。明明一向是以「心态好」自称的来着……（果然自己还是知道的吧。）

复赛

试机打了个 SAM。好像以前从来没有用拼音默写歌词呢。

Ren5Jie4Di4Ling5%。

先看看题吧。T1 应该不难。T2 n2^k\alpha 能过吗？T3 也许不难。T4 是计数，虽然一眼看过去没啥头绪不过先别急。

来开 T1，哦怎么 n 是偶数这下一点细节都没有了。不过对吗。稍微花一分钟证一下。不会爆 int 吧。写写写。我怎么忘记我以前的习惯是大样例都拖到选手文件夹里这样不用来回切文件夹了，坏。

来开 T2。想一想，真想不到不带 2^k 的东西了吧。那就写吧。。大样例……怎么不满，这还要跑 0.3s 是不是倒闭了。造个随机的极限数据，0.7s 不到。原来是之前的瓶颈在排序导致的。再测几次，怎么 RE 了……看下 sanitizer，原来是数组开小了，应该开 n+k 的。CCF 机子应该稍微也能比 NFLS 机子快一点吧，就算有更优的做法也等会儿再来看吧。

来开 T3。总之就是对中间不一样的部分分类然后两个前缀匹配。嗯我一开始没看到空间限制是 2048MB，于是质疑连个 Trie 树都建不出来 ACAM 更没法建这咋做啊，要不要直接对字符串排序求 lower_bound 啊。后来发现了绕了一大圈还是写了 Trie 然后写了一大坨代码，导致本来打算给 T4 留两个小时的，大概超了一点点时间。

来开 T4。感觉一下子想不到一个多项式复杂度的做法啊，咋刻画啊。想了一会儿发现从前往后考虑的话，不符合条件的人会保持不符合条件。对“要求符合条件”容斥就可以了。去上了个厕所回来推完写完。现在是下午 5 点 10 分。

本来想拍一下 T3 但是感觉自己也造不明白有强度的数据，于是对着代码肉眼观察以及再以各种方式测了测样例。就这样吧。

后来和大家讨论才发现原来 \sum |s_1|+|s_2|\le 5\times 10^6 意味着 \sum |s_1|\le 2.5\times 10^6，这么魔怔啊。原来好多没有意识到 |t_1| 不一定等于 |t_2| 的，这个是不是样例 2 就有来着，不过 CCF 真的会卡很多这个的分吗。

出分了。怎么 T3 真的被爆了。100+100+65+100=\boxed{365}。

线段树数组怎么只开了一倍，这下不得不承认树状数组的高贵之处了。

嘟嘟嘟。没啥好说的了/fendou