CSP 2025 游寄

· · 生活·游记

坐标 GD。

今年能不能拿个蓝勾啊。

Week -?

不小心把 J 的费缴了，来都来了就去打吧。

过初赛了。看来今年没有 xxs 难度还是没变。

但是 @Nukigatana 好像忘记缴费了。RIP。

Week -? ~ -1

10 月全天停课。在 jf 打教练们精心准备的 NOIP/CSP-S 模拟赛。

学校斥巨资新建了电脑室，为了让我们这些 sky 的可以安心训练并方便管理。新机房在四楼，叫了几个苦力（包括我）从一楼抬新主机和显示屏上去，我们以十分有序协调的分工合作，花费 0.5h 快速地完成了任务。看主机配置好像不低于我家笔记本。本来以为立马就能用，但实际上一直以在维护的名义不让用，只在最后几天由于原训练机房要布置考场才来这里用。

开了什么动员大会，给我们讲述了金牌学长 czz 的事迹。原来喝水不能用大水壶，想题不能站着，不能去厕所不然会被科学教育发展中心主任视键，不能打篮球却必须跑操，不能去小卖部买早餐不然会被羞辱，上午打模拟赛时不能离开座位。并且还需要在这样的环境下让我们进入省队拿到金牌，好让一位父母健全的人笑着和北大签约，如果高一没拿省一就必须退役。太震撼了。

模拟赛的质量还是太高了。从来没有外国题做得却都是 CF/AT/JOISC 的原题。断网测试无法下载大样例，无法加载题目图片，无法看到强制在线题目的解密方式，出的都是高质量而非经典题，如弹飞绵羊。

随后是体艺节。不让我们观看晚会却必须参加展演，由于没有好的 idea（本来提议朗诵追忆，但被班主任以何意味的态度驳回），所以只得表演了第三套广播体操。早上的运动会那更是不可能看的。

总而言之，度过了欢乐的一个月。

Week 0

最后一天复习了一些板子，看了之前的笔记。特别复习了比较垃圾的字符串。

11.1 终于还是来了。考场是本校，而且居然是曾经平常训练的电脑一室。考个试跟回家了一样。

上午

当练手。

看 T1，题面好长。五分钟写完。

看 T2，数据范围好小，在暴力模拟和数学方法之间徘徊不定。最后还是用了 lower_bound 求排名。但是被 greater<int>() 调了一会。

T3 似乎比去年水。区间无交，直接想 f_i 表示以 i 为右端点的答案。又是经典异或自反性，直接 unordered_map 优化做完。看到 2^{20} 好像有点大，忘了可以直接开数组。

本来想直接开睡，但是看了眼 T4 好像也有点意思。遇序列不决先排个序。想计数 dp，这个时候以为每轮加新木棍都必须和之前的木棍满足条件，于是记 f_{i,j} 表示考虑前 i 根且必须选第 i 根加入，然后总长度为 j 的方案数。不难发现 j>5000 时状态无效必然可行，所以把所有这些的方案压到 f_{i,5001} 上去。

但是直接转移好像复杂度不对，于是用 @__Legends__ 大佬教的 trick，再记一个 g_{i,j} 表示不必须选第 i 根，然后 f_i 就可以从 g_{i-1} 转移，g_i 可以从 f_i 转移。这个时候复杂度对了。

然后一测样例又发现不对，中途加入如果不合法，后面再加可能又合法了。于是加一维 f_{i,j,k} 表示选了 k 根棍木，相同的操作，直接把 k\ge 3 压到 k=3 里去，但是此处记 k=3 表示 k\ge 3 且当前不合法，然后记 k=4 表示 k\ge 3 且保证当前合法。这个时候就能转移了，加入如果不合法就转移到不合法上去，否则转移到合法上去，并且合不合法都能用来转移。最后答案直接统计合法的即可。顺利过掉所有大样例。

捣鼓 noi linux，然后无聊写出了一个 tester.cpp，可以实现只要把大样例包和这个放在一起就可以自动给程序测大样例，还挺好玩的。

预期得分 100+100+100+100=400pts。

随后出考场问到 @Alexandr 居然没 AK，分期鹿大神 @Fenki_lo 的 T4 写了容斥，还有严队 @yanzihao6688 用了 0.5h 就 AK 了。膜拜。

中午

饭堂人好少。

@WJYwangjingyi 完金叶大佬 T3 数组开小了。

中午回宿舍看了一中午龙族，亚历山大抢我的手机玩。

下午

本来策略是稳两题然后冲部分分。

看 T1 有点熟悉，好像模拟赛做过二维版本的。纯贪心的话，记三个 cnt 表示统计对应列中有多少行的数是作为三元组的最大值，然后选的时候优先选这些。如果对应 cnt 不超过 \frac n2 就直接选这些，剩下再选最大。然后被样例三 hack 掉。

于是又想想想，不知不觉就过掉了 40mins。我本来策略是这个时间想不出 T1 就去看 T2。因为研究发现前几年 T2 小于 T1。

T2 什么抽象玩意，我考前忘记复习 MST 了。但是 kruskal 太好背了，所以还是会的。一开始看错题，以为镇也是里面一个城，打算暴力建边。然后仔细一看镇是单独的。又发现 k 很小，或许能 2^k。但无论如何都只能想到 \mathcal O(n^2) 建边。有可能是 kruskal 重构树吗？但并没有最小权最大之类的东西。拼尽全力无法想到，只能回去看 T1。

再来看 T1 发现贪心策略问题在于 cnt 大于 \frac n2 时。大胆点猜最优策略一定是把 cnt 最多的列都选了，然后就考虑已经选出 \frac n2 个数后，再依次加新的数，判断什么时候新加进来的更优。

假设考虑第一列，显然应按 a_i 降序排，并且优先考虑 a_i>\max(b_i,c_i) 的。如果已经选了 k 个，要考虑该不该选第 k+1 个，那么它更优的条件就是存在一个 j 使得 \max(b_j,c_j)+a_{k+1}>a_j+\max(b_{k+1},c_{k+1})，转化一下变成 \max(b_j,c_j)-a_j>\max(b_{k+1},c_{k+1})-a_{k+1}。变成相同的形式了！继续想，既然这样新选的更优，那就考虑怎么样不让新选的优，这样原本选的就是最优的。简单推一下就发现必须要求 a_i-\max(b_i,c_i) 降序，然后按这个排完序后再贪心地选前 \frac n2 个就行，其它列也是类似的。调调调，过掉所有大样例，直接不管了。这个时候已经过去了 1.5h。

再来想一下 T2 吧，但是毫无思路，于是看性质。c_i=0？那我直接暴力建边 i\xrightarrow{a_{k,i}+a_{k,j}} j 然后跑 MST，复杂度 \mathcal O(kn^2m\log m)。而且刚好 k=0 也可以这么做，如果 CCF 机子可以跑 2e8 的 sort 就能拿 40pts。感觉不低，赶紧先把后面的暴力分拿多点。

看 T3，说好的没串串呢？还好考前复习了 KMP。先求每个模式串的 border，然后每个询问暴力让每个模式串匹配。发现能贡献必须两个文本串分别匹配两个模式串的位置必须相同，然后直接这么写。发现过不了样例，原来忘记判 x 和 z 相不相同了。串长度相同就比较好办，无需哈希直接记前后缀对应位置相不相同。然后匹配时如果到了一个合法匹配但是 x 不相同，那么往后匹配肯定也不同，可以直接 break，后缀同理。过掉比较小的大样例，直接不管了。（这里我好像挂分了，我似乎写的是如果后缀不同也直接 break 了，但这好像是错的，因为匹配是从前到后的。丸辣！）

看 T4，排列计数好像做少了，特殊性质没有任何思路，直接打完 8pts 开溜。

继续想 T3。多串匹配不会是 AC 自动机吧？但这玩意不是 NOI 级吗？更不能是什么 SAM 之类的吧。还能是字典树不成？

感觉 T2 是最能蒸的了。但是没法想到跑 MST 以外的东西。

我常常追忆过去。 我在草稿纸上写道。

最后 30mins，检查了一下 freopen，虚拟机上编译了一下，似乎都没问题了。

预期得分：100+32+10+8=150pts。

结束了。

无论如何这都结束了。无论考的好还是差，无论这段时间努力或否，都暂时地结束了。

原来都不会 T2 啊。那没事了。

群里讨论，莱珍兹神明差点就 300pts 了。高香蕉也 320pts 了。你们都好强。

但是听说 1= 线好像在 150 左右？？

先假装自己能进 NOIP 吧。

后记

出分了，J 实际得分 100+100+90+100=390pts。

T3 初始化写错了，成功挂分，饮恨西北。/fn

S 实际得分 100+56+25+8=189pts。

神秘 T3 没卡 |t_1|\not =|t_2| 就算了，就我这神秘 kmp 还能反向挂 15 分？？神秘 T2 怎么又反向挂了 24pts？？原来是 CCF 数据大手子，失敬失敬。

但是一车同学都 200+ 了。/fn

能不能去 noip 啊。

别卡 7√。

别卡 7√。

别卡 7√。