CSP-S2025 右击

· · 生活·游记

省六：

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

前言：

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

Day：-1~0：

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

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

Day1:

早上本来想补一道数据结构练练手，结果 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 球，然后又熬夜了。太不健康力！

Day 2:

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

Day 3：

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 呢？