2025-2026 赛季游记

· · 生活·游记

2025.9.20

初赛。前一天晚上瞎搞，比较晚。第二天中午起来，吃个饭，看看 SCP 的模拟赛，诶怎么有一题和答案不一样，想不懂为啥。

下午打 CSP-S 复赛，随机看到了一些同学。

复赛简单。但是改了两次依然无法通过编译的程序，令人汗颜。

目的是不是去重？不知道，争议挺大。 反正，看上去只要不被做局，应该能过。 # 2025.11.1 这一个月多一点的训练，基本上还算认真吧。虽然偶尔会被模拟赛 T2 卡住，怎么回事呢 其实本来不想写 CSP-S 复赛游记了，真的太耻辱了。 T1 我开场想了 5min 才会。不知道在干啥。 T2 mst 做多了，$m$ 条边优化到 $n-1$ 条边是容易的，发现只会 $2^k$，发现 $k\le 10$，直接开始写，枚举乡镇集合，$O(nk)$ 条边放一起排序。大样例 3 挂了。想不出来做法正确性问题，挂了一个拍子。发现是枚举 $S$ 的时候有类多测不清空状物，改了一下，过了。但是跑得慢。想到可以用归并排序把 $\log nk$ 优化到 $\log k$ 但是鉴于已经浪费了一个半小时，遂暂时放弃。 T3 看了题，没啥思路。 T4 看了题，手模了一些东西，有点思路，感觉至少能写不少部分分。 上了个厕所回来看 T3。下面请看我的传奇思考过程。 首先不久就想到取出中间的最短的覆盖了所有不同位置的串，可以哈希，使得对于一个询问串只有若干 $s$ 能匹配。此时就是，如果 $s_1$ 能和 $t_1$ 在对应的那个位置匹配上，就可以计入答案。 首先，能不能直接匹配？显然是不太行的，因为有可能 匹配上了之后 $s$ 缩的位置和 $t$ 缩的位置不一样，匹配上了没有意义。遂放弃。赛后知道，实际上在缩起来的位置放一个**特殊字符**，就直接做完了，一个极其好写的 ACAM 做法。 那既然不能直接匹配，考虑这个串的左侧，要求 $s$ 的左侧是 $t$ 的左侧的一个后缀；$s$ 的右侧是 $t$ 的右侧的一个前缀；容易想到建立两个 Trie 树，答案即为同时出现在两条路径上的点的数量。然后就想不到了。实际上，赛后知道，只要离线下来，dfs 左侧 trie 树，每次到一个节点就在右侧 trie 树上用 bit 维护 dfn 序，这样每一个信息只会加一次删一次，直接又做完了。 总之，两个做法我都只差最后的临门一脚。但是想不到就是没想到，总不能空着吧，写了一个超级弱智的 $O(nq)$ 暴力，还附加了一些 $\log$，感觉 40pts 都不一定有啊。大样例跑的还挺快，不过是人都知道大样例很水，$n,q$ 都很小。 而且赛后出来发现 T3 没判 $|t_1|\neq|t_2|$，又睡了。 T4 暴力随便打一打，最简单的前两个点和 $m=1$。其实应该还能搞更多的，不过没时间好好想了。 100+[0,100]+[0,~40]+20，反正 WC 是去不了了，NOIP 希望没有问题吧。 不慌，保持信心，NOIP 再战。 出分，T1 挂成 70，hyw？T2 80，算是最差的结果，T3 50，最差的结果，T4 没法更差了。 何意味何意味何意味何意味何意味何意味何意味何意味何意味何意味何意味何意味何意味何意味何意味何意味何意味何意味何意味何意味何意味何意味何意味何意味 没事，挂分攒 rp，反正进 NOIP 了，去年 NOIP 能三题，今年总得进步吧。