CSPS-2025 |t1| != |t2| 记

· · 生活·游记

DAY -INF

上高中，然后停课。
感觉自己的思维明显慢大家一拍，模拟赛里大家十分钟就可以切掉的题我要在自己的思维里绕半个小时。

DAY -INF/2

S 组初赛只有 85，菜昏迷。

DAY -1

学校举办了校运会，初中跟高中的校运会是不同日子的，去年我们初中，校运会下一天 CSP，今天我们高中了，校运会下一天还是 CSP，咋这么巧。
不过对于停课的我们而言，这些东西与我们无关。

DAY 0

上午很晚才起，训了一会 florr。
在中午去考点的车上复习点双，不过应该不会考吧。
到考点了 @yangmingshuo114514 凑过来问我 AC 自动机怎么写，我突然发现我好像也不会写 AC 自动机了，等会要是真考串串就完了。

14:20

进考点。

14:27

发了压缩包，密码是人杰地灵。
直接扫视题目。
t1 不是 dp 就是贪心。
t2 图论。
t3 是串串...等等，串串？！再一看，不是计数，而是匹配问题。开摆，等死。
t4 是一个 n^3 做法，长得就一副我不会做的样子。

14:30

开 t1，还没看懂题意，旁边已经一堆人开始写了，我去，这题不会是简单题吧，我怎么看不懂。看懂题意了，是不是如果每一个都取最大的，那么 \le \frac{n}{2} 的就只有 1 个集合，然后这时候从这个扔一点出来，扔损失最小的就好了？好吧还真是简单题。

14:40

写完一遍过大样例，懒得写拍子了直接看 t2。
谔谔，怎么是求最小生成树。看了下数据范围发现 k 特别小，只有 10，这是何意味，为了防止 n\times k 过大吗？
这题是不是要想办法把建立乡村转化成点之间的边然后跑 prim 或者 Boruvka？
想了一下发现很难把乡村弃掉直接转化成边。于是发现好像可以枚举乡村，然后直接最小生成树就是对的。但是这样复杂度是 O(2 ^ k mlogm) 的，完全无法接受。
又看了一下数据范围，发现 n 很小，只有 10^4。也就是说，在枚举乡村的前提下，正解复杂度应该是 O(2^kn) 的。
好像也没有其他的可能了，因为要求新图的最小生成树，要么在新图上跑，要么就在原最小生成树的基础上修改。
等下，从原最小生成树的基础上吗？是不是我只保留最小生成树上的边就对了，这样复杂度就可以做到 O(2^k nk\log nk\alpha(n)) 了，虽然这样还是 10^9 级别的，但是应该离正解不远了。
证了一下发现这个结论是对的，但是怎么把这个 \log 去掉呢？在排序的时候，一般用桶排做这个东西，那其实把所有边拿出来排序，然后在里面扫一遍就可以了，那这样就可以做到 O(2^k nk\alpha(n+k)) 了，这样是 10^8 的，卡卡常绝对能过，再加个剩余联通块数量 =1 自动 break，应该能过。

16:00

大样例挂了还输出了一堆 0，好吧原来是我的初始联通块个数设错了，改一改就过完了。
开 t3。
首先替换实际上有用的就是中间真正改变的部分，所以询问要关注的也只有中间真正改变的部分相等的替换。那问题就转化成了，问有多少个字符串，使得字符串前一部分是文本串前一部分的后缀，后一部分是文本串后一部分的前缀。
一开始想到可以同时维护两个 trie，然后加加减减容斥一下，发现这个思路完全不对。于是思考只维护前缀的 trie，然后在每个节点上再维护一个 trie，但是想了很久完全不会节点之间下标的移动。
后来发现我完全不会 trie 计数做这个题，于是把目光转向了子串匹配。
发现每个替换一定会在原串中出现，但是怎么样避免这个替换在原串的其他地方出现影响答案呢？
原来直接往替换中间加一个特殊祖字符，再往原串中间加一个特殊字符，就可以直接多模匹配了，那这就变成 AC 自动机板子题了。
但是我上一次写 AC 自动机已经是大半年前，已经完全不记得怎么写了。
于是在考场上直接凭着回忆现推。

17:00

推出来了 AC 自动机怎么写，于是开始写。

17:40

写出来了，测大样例发现跑最后两个大样例时间特别久，一个要 8 秒，另一个要 12 秒，我输出了查字符串的最内层循环执行次数，只有 8\times 10^6，为什么会跑这么久呢？

18:10

把代码里所有的内层循环的执行次数全统计了，输出的时候很震惊，居然爆了 int，也就是说瓶颈不在于查询，而在于其他部分。也不可能是插入部分，于是我把目光转向了清空，发现我没有清空 cnt，唐飞了。
改完之后大样例跑的飞快，于是急急忙忙看 t4。

18:20

只会暴力排列了， s_i=1 的时候直接输出阶乘，急急忙忙写完开始检查文件。

18:30

结束了，除了考场跟大家一对才发现，t4 输出阶乘就不应该有分，因为存在 c_i = 0 的情况，也就是说我 t4 就只有 8 分了。
期望得分： 100+100+100+8=308

21:00

看 LA 群发现在讨论题，点进去一看 |t_1|\neq|t_2| 天都塌了，瞬间感觉自己两个小时的努力白费了。
可能会 RE 的部分：

pair<string, string> calc(string s1, string s2, int &from, int &to){
    int mn = s1.size() - 1, mx = 0;
    rep(i, 0, s1.size() - 1){
        if(s1[i] != s2[i]){
            mn = i;
            break;
        }
    }
    per(i, 0, s1.size() - 1){
        if(s1[i] != s2[i]){
            mx = i;
            break;
        }
    }
    from = mn, to = mx;
    return {s1.substr(mn, mx - mn + 1), s2.substr(mn, mx - mn + 1)};
}

我直接用 s1.size() 扫 s2。

DAY 2

在上午把自己赛时的代码重新打了一遍，发现我的代码顶着如上的数组越界过掉了洛谷的民间数据没有 RE，交了云斗也没有 RE，于是开始祈祷 ccf 能够无视我的 UB。

DAY 5

出分了，良心出题人没有放 |t_1| \ne |t_2| 的数据，不知道是不是因为挂掉的人太多了。
总分 100+100+100+8。
后来发现其实并查集如果只写路径压缩是可以被卡到 O(\log nk) 的。
谢天谢地，一分没挂。
感谢 ccf 少爷机。
感谢一切。