CSP 2025 游记
本文节选自 @toolazy 的 CSP 2025 游嘻，有删改。
删去部分与赛程无关的文本，并删改了大部分尖锐/恶俗词句以符合 征文标准。
\text{FriDay }0
收拾东西启程，进攻西站。高铁有插座很舒服，坐不认识的学弟旁边，二人自娱自乐，赫赫。
4h 后下车了，收拾东西撤退，还是一样的景色，向汉庭进发。
分房，和 lzl 一起。回房间歇息片刻后出发吃饭，见到 rz 了。
步行，中途 rz 讲了好些题，记着多少写多少。
定义函数
f(n,k)=n^{2^k} 。现给定动态图，连边删边。带点权，支持单点改点权。每次查询某联通块的
\sum f(a_i,k) ，k 由每次询问给定。答案对
998244353 取模。
太诡忧了这题... 你说，为啥
如果全局
k 固定那就是线段树分治板子。接下来我们考虑欧拉降幂，哈哈
\varphi(998244353)=7\times 17\times 2^{23} ，循环节很短，最多119 但实际只有几十好像是。暴力全部记下来，做完了。
（咳咳你家 CSP-S T1 模拟赛放线段树分治... 我要点名表扬【数据删除】）
给定一个
n ，最大化k 使得存在a\neq 1 满足a^k\mid n 。在此基础之上最大化a ，将其输出。
如果你能进行快速质因数分解那显然就秒了，但直接 Pollard-Rho 并不是题解本意。
我们枚举
k 看起来似乎非常乐观，a\neq 1 的话k 最多枚举到64 。设 $n=a^2\times b$，则： $$ \Big(\min(a,b)\Big)^3\le a^2b=n $$ 枚举 $a$ 到三次根号，再枚举 $b$ 到三次根号即可。 这个思路似乎很具有启发性，可以扩展？
咳咳其他的忘了。那就继续闲话。
吃饭，依旧荤菜量大管饱，依旧我来清场撑场面，经过历练的我现在已经可以吃一些辣了，呃呃希望明天不要飞起来。
饭店回酒店休息，rz 和 lzl 打铁，我打空洞。
十点半小林总查房，rz 撤退了，我改刷 B 站到一点钟，没敢洗澡直接睡了（不要学）。
床上刷手机随了两道水题，秒了，不错，信心 up。
\text{SaturDay }1
gank 起床起晚了，被林老师骂了，快快快去吃饭。
非常忌惮在考场飞起来，所以尽量吃干的，避免太油太凉。
打车去考场，十字路口堵死，直接半路下车，只留司机独自惆怅（司机：I love you so~），一年一度了属于是。
经典考场门口人太多挤散了，九牛二虎之力把人找齐，合照之后进入考场。
上午场 CSP-J
✌：有没有信心 2h ak？
lzz：呃呃听起来有点困难，3h 应该可以。
开赛前先上厕所，上完厕所后英雄归来，惊讶地发现今年一道绿题都没有。
20mins 会完感觉有点久了，变逊了；40mins 写完感觉有点久了，变逊了。
难绷 CppCodeBlocks 玩 BYO Games :: Tetris 玩了十分钟就锁一个小时，这... 哎，睡觉吧。
旁边居然监考员辅导选手写 freopen，啧，不是稀硝酸胜似稀硝酸。
一帮人在哪里这个不会那个不会，好吵啊，睡不着，有点红，提前出考场了。
愉快的中场休息时间，放条分割线。
吃饭吃饭，还是和去年同一个饭店，一样荤菜非常多。
午休为下午做准备，别人拼好床给椅子用光了，我睡地板哈哈。
怎么有人趁着午休视奸我，吓哭了。
回考场，九牛二虎之力集合，忘记拍照就进考场了哈哈哈。
下午场 CSP-S
✌：有没有信心 300pts？
lzz：努力！
哎呦难绷，怎么感觉我的座位和去年 CSP-S 一模一样，坐中间过道上了，直接被监考老师疯狂视奸。
开题开题，发现 t1 略卡，立马被周围人压力了。
嗯也许我应该掏出纸笔写写思路，事实证明这个决策似乎很正确。
先考虑纯贪心，每个人都选最喜欢的科目，如果这样子做，三个队列都没有超限，那我们肯定很开心，哈哈。
如果超限... 嗯，那 最多只有一个队列 超限，只要把那里面的多出来的人给解放掉，
n/2 的限制势必也不会让别的队列超限。直接贪心，把队列中替换代价最小的若干个解放掉就好了。
十分钟搞完，节奏很不错，合理论断上午场信心给足了。
t2 继续继续，一眼就感觉像特殊的 MST。
观察数据范围。哎呦我的妈你别笑，
k\le 10,n\le 10^4 ，直接暴力枚举选哪些村庄然后暴力 kruskal 不就对完了？
写写写，谔谔卡了一会，写了比较久，最后测测，样例三 730ms，样例四 520ms？怎么大样例反而更快呢。
幸好察觉到了这个，让我倒回去重新看了一眼数据范围：原来提供的样例数据范围根本就没满，行吧行吧那就自己随一个大样例。
埋下祸根。写完 generator 之后一测，woc 怎么跑了 4.2s，爆炸了。
不知道是不是因为本地机太蔡，但看看着感觉横竖都过不了。
尝试卡常但是浏览我自己的代码实现之后感觉没有优化地切入点，于是先 skip 了。
开 t3 喽，欸这怎么串串啊，串串我不会啊...
我们只有一次替换手段... 嗯，那么我们把 Longest Common Prefix 和 Longest Common Suffix 给找出来，中间的就是 最小差异段。
显然，
s_1,s_2 的最小差异段要和t_1,t_2 的最小差异段相同才有替换的可能。剩下要考虑的，就是最小差异段之外的前后缀，因为
s 和t 的前后缀核能没法吻合，这是我们需要考虑的。我们提前把所有
s 根据差异段的哈希值进行归类，然后接下来就是一个... 看起来很不可做的东西。
想到这里感觉要放弃了，而且我们到现在位置都还没有讨论过
欸，等下，
那么此时，显然能够替换的
(s_1,s_2) 字符串对，也必须满足s_1=s_2 。这是一个子串匹配问题！多模匹配显然 ACAM，说起来很简单，但上一次我写字符串都已经... 半年前了？
CSP 真的会考 ACAM 吗？哦原来内存给了 2G，那没跑了。
一想到子串匹配，思路一下子就放开了。
由此联想到
t_1\neq t_2 的情况。假如t_1 和t_2 都可以被拆分成x+{\rm diff}+y ，而s_1,s_2 也可以被拆分成x'+{\rm diff}+y' 的话...那，我用一个特殊字符
#替换掉\rm diff ，然后直接跑多模匹配，不就对完了吗？！
此时监考老师报时， 目前赛程 1.5h，时间很充裕！下定决心要以自己积贫积弱的码力冲击 t3，为此在此梳理了 0.5h 的思路并尝试回忆 ACAM 怎么写。
梳理完了去上厕所去，先袅为敬，调整状态（？怎么你调整状态的方式这么奇怪 x3
开写！边写边想，慢慢悠悠地写完 ACAM 已经 30mins，提前测一下。
？怎么锅了，调吧调吧，调完之后一切都会好起来的...
调 ACAM + 完成剩余部分大概 30mins，特判了
测测比（指 diff 文本对比），所有样例光速跑过。我天这把赢麻了啊。
监考老师报时，还剩下 1h 结赛。调 t2 去喽。
仔细想，怎么想也不可能和期望差异这么大啊，除非我期望错了。
欸你别说好像真错了，暴力 kruskal 好像其实是
我肯定要把
对嘛对嘛对嘛，写写写。怎么 RE 了？嗯？？？！！
嗯，兑，然后调了 20mins，我也不知道最后是怎么发现的，反正最后我发现我大样例搓错了，少输出了一条边...
与空气斗智斗勇，埋下祸根的伏笔回收了。现在重新一测，额，1.6s... 快了很多但... 依旧难说。
接下来开始自掘坟墓。我脑子一塞出了个馊主意，欸多路归并不用
写写写，哎呦怎么 CE 了，那算了换个实现... 哦现在没问题了，然后跑了 3.9s...
6，花了半个小时优化了 。死了啦，倒档吧。
我！怎！么！Con！trol！Z！倒！不！回！去！了！
我！中！途！怎！么！把！编！辑！器！关！了！
哦吼炸了，现在不是优化 是真的越优化越慢了。
尝试花最后半个小时重写一遍，结果重写反而挂了，嘶哈鸡皮疙瘩起来了。
好吧最后 5mins 实在没把第二版
希望能仗着 t3 苟进 NOIP，呔，太他妈失败了。
这个悲伤的故事告诉我们：代码要常备份，尤其是在改思路/开始卡常之前；还有就是脑子没问题就别关编辑器...
轻松离场，放条分割线。
九牛二虎之力终于集合，rz 似乎没考好但不上心。他一路上尝试向我解释 t4 但似乎失败了。
rz 还说他 t1 没看到
周围人貌似都没做 t3？很尴尬了啊，这明明就是 ACAM 板子题的来着...
吃饭，直接在学院食堂里面吃的，出乎意料的不错，比外面便宜多了，量大管饱。
有人边打洲边端汤锅然后把锅给打翻了，我不说是谁。
回酒店。lzl 拿了卡就先润楼上了，我在楼下和三中过来等火车的聊天。
后来 rz 找廖凯要去散步，我跟上顺便会面了 jx 第一大帅哥。好吧感觉三个人的舞我还是别跟上了，于是半路道别最后还是回了酒店。
和 lzl 打游戏到很晚，后来 lzl 睡了，lzz 继续打洲，我刷 B 站，一直刷到了凌晨五点？？？（别学）
梅姨阁诗人，刷新个人熬夜记录了。哎呦昨天打比赛说没敢洗澡，今天还是得洗一下。
昏沉睡下，不知道 lzz 睡得好不好。
\text{SunDay }2
起床，赫赫似乎再次起晚了，不管了好好吃饭。
老配置，炒面煎蛋没包菜，那算了懒得管了，哦哦煎饺火腿肠不能少，油条豆浆，咳咳，豆浆换牛奶试一试。
柠檬茶？来一杯。口区难绷了怎么这么苦，那我必须给 lzz 尝一尝了。
归途没什么意思，主要是这一次坐的是特快，没插头，对于现代人来说着实是没活。
下车了，就这样吧，梦醒了。
后记
今年绝对是我最 win 的一年，状态很好，自测 S 组 300pts 没跑了。
upd：J 400 S 300 一分不多一分不少，爽啦。