CSP-S2025 右击

11.05，幽默链接查分，$100+100+100+20$。

打完 D 类应该已经 AFO 了。暑假没有任何集训，回去学 whk 了
但是开学后又莫名其妙被抓回去集训了
第三周还去打了 sb 市赛，被 D1 唐诗出题人用 bitset 卡常题调教了，喜提 2=
感觉集训就是摆烂了快两个月（（（

通过一些手段，周四下午回家了。晚上刷了会手机，然后发现一本很有意思的书，于是阅读到两点，成功熬夜了（（（

第二天起来，早上随便补了一下前几周杂题选讲的题，然后下午开始摆烂，玩 MC 看 b 站，爽似了。

早上本来想补一道数据结构练练手，结果 WA on 24，破防了。继续打 MC。然后吃午饭，打车去六中。

是的，赛前一点板子没看（（（

进学校后和 gzy 还有 gzy 一起刷手机，然后就上楼了。居然不让把咖啡带进机房！！！

T1 看着像贪心，于是没有仔细想就写了，过样例就不管了。
T2 $O(m2^k)$ 很显然，枚举要改造的点，然后视为普通点做最小生成树。但是好像过不了。但是发现加入更多边后，连通性肯定只会变强，所以原来不用的边加入新边后肯定也用不上。于是 $O(nk2^k)$，上个厕所回来调一调就过了。
只用了一个小时。优势在我！（（
T3 一眼看过去感觉根本不能做，一时间只能看到 $O(nq\sum len)$，闹完了。但是后来发现一对替换一次只能贡献 $1$，因为 $s1_i \ne s2_i$ 的地方必须与 $t1_j \ne t2_j$ 的地方一一对应，所以最多有一个刚好卡住的位置。更进一步，设一对字符串（$(s1,s2)$ 或 $(t1,t2)$）第一个、最后一个不相等的位置分别是 $l,r$，则只有 $r-l$ 相同的 $(s1,s2),(t1,t2)$ 才会有贡献。这样就是 $O(nq)$ 的。然后突发奇想：将两个字符串的字符交替放置，组成一个新串（比如：$S'=s1_1+s2_1+s1_2+s2_2...+s1_{len}+s2_{len}$，$+$ 表示拼接），那么一对 $s$ 对 $t$ 有贡献，则必然有 $S'$ 是 $T'$ 子串。但是感觉可能匹配的时候会错位，比如 $s1_i$ 匹配到 $t2_j$ 上去了，所以索性在 $S',T'$ 奇偶位置后面跟一个不同的特殊字符。直接上 AC 自动机。时空复杂度 $O(len\sum)$，有点极限。
写了快一个钟，主要是有很多很唐的情况比如 $s1=s2,|t1|\ne|t2|$ 等等。结果过掉前三个样例后第四个被虚拟机的终端"已杀死"。何意味啊？？？一开始以为是 string 的锅，换成 char 数组，然后 queue 也手写，总之一切都是静态空间。结果还是炸了。assert 也没有说 Trie 树越界了，fsanitize 也没有 RE，非常诡异。匆匆忙忙半小时，然后决定去 Windows 上测一发，结果过了？？？然后有检查了一遍，感觉没问题？于是决定摆烂了。
此时还有一个小时多。想了十几分钟啥也不会，于是先把 T4 $20$ 分状压 DP 写了。然后发现 $m=n$ 很唐，写了。还剩半个钟开始思考 $m=1$，想到可以求出一个都没有招到的情况。延迟钦定 DP，设 $f_{i,c1,c2}$ 表示第 $i$ 天后有 $c1$ 个 $c< i$ 的人没有入列，有 $c2$ 个位置要填 $c\ge i$ 的位置。转移时如果要填一个 $c\le i$ 的人则乘上 $c1$ 然后 $c1-1$；否则 $c2+1$，此时要满足 $s_i=0$。然后在该天结束后把所有 $c=i$ 的人加进来。枚举多 $k$ 人要填进前面的 $c2$ 个位置，然后 $c1+t_i-k,c2-k$。由于 $k\le t_i,\sum t_i=n$，所以总复杂度 $O(n^3)$。但是没有调出来，流泪了（事后回忆应该是少乘了一个组合系数
估分是 $100+[80,100]+[0,100]+24$，何以谓（what can I say）？

晚上去打了 2h 球，然后又熬夜了。太不健康力！

颓了一整天
晚上回来问了几个人，说应该只是虚拟内存没开够，闹麻了

666 早上迟到吃到警告函了（
写了一整天信（校际信使活动）

然后晚上花了一小时不到补 T4。
发现直接在上文基础上加一维 $j$ 表示拒掉的人数。发现转移的时候 $c1-c2=\sum\limits_{p=0}^{j}t_p-i$，因此记录一个 $c1+c2$ 即可。总复杂度 $O(n^3)$。
呵呵。如果没有虚空调试 1h 应该就做出 T4 了，那就 AK 了？
最终幻想

所以为啥 T4 $24 \rightarrow 20$ 呢？