2025 CSP-J/S复赛游记

__LBX__ · 2025-11-02 13:34:16 · 生活·游记

Day ？~ ？

打提高(存疑)模拟赛，数学烂完，只会模版题。常年[0,100]感觉要炸

教练说题太难，给我们换成了普转提难度，被同机房大佬薄纱，常年[100，300]感觉要完

地狱级模拟赛，打了1个小时T1只有30pts，这下信心赛了

发现昨天比赛T2很简单改出30+100=130依旧感觉要炸，最后看了下kmp，manacher和割点的模版和教练给的注意事项(伏笔)。
感觉自己完蛋了

T1水

T2显然有数学做法，想到教练给的注意事项，于是选择先去看一眼数据范围，发现可以模拟

T3首先肯定要做前缀异或和，然后就是dp，快速过掉小样例后发现大样例输出比答案小相当多，应该是转移问题，处理dp值即可，此时已经过了近1h

T4肯定要对长度排序，然后自然想到O(n)枚举让每个数都去当最大值算贡献。可以用dp求方案数，然后树状数组求方案数的前缀和。
发现a[i]小于等于5000，所以可以对凑出5000以上的数的方案数特殊处理。复杂度O(n^2 log(n))，拉满得炸，但我觉得炸不了(

花了近半小时打完后发现过不了最后一个大样例，用10min乱搞啥也没搞出来。平复心情后开始分析，只错了最大样例说明问题出在对5000以上的数的方案数的特殊处理上,打出hack并调好后发现时间还剩1h30min，于是开始摸鱼，结果在最后10min发现T3的hack，紧急修复

出赛场后估分100+100+100+[80,100]=[380,400]，担心自己T4爆TLE，但经过我一通并不严谨的分析后，我感觉复杂度是拉不满的

感觉题目难度是红橙黄绿
实际难度：橙橙黄绿
低估T1了，不过T1有数组确实是橙

中午没睡，到考场后有点小困
T1肯定是贪心，先把所有人分到最喜欢的社团然后再踢人，但容易看出不能直接踢贡献值小的，应该优先踢被踢后贡献值亏损较小的，想到教练给的注意事项说一定需要先看小样例验证做法，然后去看样例发现样例3直接体现出这点了

T2汗流浃背了，先想到可以状压枚举每个村庄选不选，然后暴力跑MST，接着去看了眼T3，感觉是AC自动机，吓哭了。
于是又回来打T2，发现最终答案中的城城连边一定是原图MST中的，优化到O(mlog(n)+2^knklog(n))并卡了常，估[64,80?]

T3有些吓人，发现哈希可以打10分于是开打，发现一直对不了，调试时发现哈希数组里的值总是很大，30min后意识到是数组下标写反了，气笑了

T4看完题面后感觉好像比T3简单(虽然我肯定都不会做)，打个简单的8pts暴力走人

最后时间全部用在了卡T2上，估分100+64+10+8=182

感觉题目难度是黄蓝黑紫
实际难度：绿蓝紫紫
低估T1了，不过T1有贪心确实是绿

洛谷估分，
J组 100+100+100+100=400
S组 100+84+35+8=227
不过洛谷的数据好像是随机生成的，所以实际S组T2应该拿不了84分，而且我T3好像数组开小了，只开了10分数据范围的大小，但后面又开大了点，不知道拿不拿得到20+

GD初二蒟蒻，希望能过1= qwq