芝士csp2025游记

· · 生活·游记

呃呃呃面到了一些大佬，然后就进场了。

赛前敲了个 miller rabin，不知道为啥就是闲的。

开题，这个 T1 好像直接贪心就行了，看了一下 n 是偶数，那么直接让每个人都取最大的，然后对于超限制的改几个就行了🧐🧐🧐。写一下，嗯，好像不对，如果 n 是奇数怎么办，想一下其实最后特判一下就行了，代码有些难写🤮🤮🤮，写写写，怎么过不了样例😭😭😭，哦原来 n 是偶数，ctrl+z ctrl+z ctrl+z，过所有样例了，此时过去 30min。

这个 T2 能不能爆改最小生成树🤔🤔🤔，怎么 k\le 10，那直接枚举 2^k 种，然后每次跑一个最小生成树，呃呃呃，这个是不是会 T。发现这个最小生成树只保留之前最小生成树的边就可以了🤓🤓🤓，那每次从之前一个状态转移过来，跑一遍最小生成树，时间复杂度 O(m\log m+2^k n\log n)，感觉应该跑过是不成问题的，开考 (1+eps)h 时写完了。

这个 T3 看一下，串串题😋😋😋😈😈😈，发现一个字符串最多计入答案一次，直接找到第一个不同的位置对上暴力 check 就行了，这咋维护🤔🤔🤔，感觉前后搞个 bitset 求交？不太好做，对 S 长度根号暴力？这个是简单的但不感觉能过，时复大约是 O(len \sqrt{n}) 左右。想了半个小时左右，想到了预处理 trie 加字符串哈希加二分的做法，时复 O(len \log len) 左右，4:30 开始写写写，写了 1h WA 在了第三个样例上死活调不出来，并且怎么我本机 5\times 10^6 的双模哈希预处理就跑了 0.7s 😱😱😱，这能跑过去我吃，此时已经 5:30，怎么办还有 30min 比赛就要结束了，我 T3、T4 还一分没得呢😭😭😭，看了眼 T4 随便胡了个 O(n!) 暴力上去，T3 胡个暴力 O(len^2) 双模哈希上去，我 WA 的样例 3 测不了，姑且认为是对的吧，检查文件，抄文件名，在 5:55 的时候把页面保持在了桌面，等待死亡的来临。

呃，都 6:02 了，怎么还没收文件😰😰😰，坏了，比赛怎么是 6:30 结束的，看了看 T4 s_i=1 的特殊性质，发现不会做，赶回来写 T3 O(n len) 暴力哈希，怎么还是在第 3 个样例上 WA 了，调到比赛结束前 3min 也没调出来😡😡😡。

倒闭了倒闭了倒闭了😢😢😢。

这辈子再也不喜欢串串题了🤬🤬🤬。

然后事实上呢。

我本机的速度跑得贼慢，我那时复应该完全可以跑过去😠😠😠😠。

然后我 T3 把 S1 S2 两个字符压在一起的，所以我的取值有 676 种，然后我取的 bas 是 327😭😭😭😭😭😭。

所以这就是我的 csp2025 游记🤕🤕🤕。