CSP-S2025 游记（Another Version）

Tiat_Siba_Ignareo · 2025-11-03 15:50:15 · 生活·游记

什么魔怔场/qd/qd/qd

先开 T1，发现不会做。真的是，太幽默了！

然后飞速写了一个贪心发现假/xk

瞪了一段时间发现每个人只会选最大值或次大值，又瞪了 30min 才瞪出来怎么做/qd/qd

此时已经过去了 1h。然后开 T2，一眼会了一个 O(2^knk\log (n+k) ) 的做法，然后想怎么优化，以及带不带 2^k。结果思考了 1h 无果，就写了一个幽默大常数 O(2^knk\log(n+k))。

然后开 T3。一眼会了一个 O(qL) 的哈希，这怎么这么像多模匹配？但是提高组应该不考 ACAM，先相信不考。估计是个 ds 题吧。于是打了一个 50 分暴力。

时间还有挺多。开 T4。看起来好难，于是打了一个 8 分爆搜，剪了剪枝。

估计是个 dp 题吧。试试 dp。定义 f_{i,j,k} 表示面试了前 i 个人，走了 j 个，有 k 个满足 c \leq j。诶我怎么不会放 j+1，一定是假了吧，干脆不去想如果是 c>j 怎么维护了，T4 肯定不会是这么弱智的朴素 dp 吧，不如想想怎么打暴力。

然后打了个 4 分，之后就没拿分了，离场。

总结：喜欢乱排题目顺序的【】，愿你们的【】在【】相遇。