CSP-S 2025 游记

· · 生活·游记

写在前面

耻辱下播，丢脸了。老年选手晚节不保。

感觉主要是策略问题，打得畏畏缩缩的导致最后化身小丑。

UPD：T3 L\sqrt L 冲过去了，而且没卡 |t1|\neq |t2|。

但是小丑的是我手写的哈希函数导致 hash table 慢了几百毫秒：

struct MyHash{
    const int mod=998244353;
    inline ull Mixed64(ull x)const{x^=(x<<13);x^=(x>>7);x^=(x<<17);return x;}
    size_t operator ()(ull x)const{return Mixed64(x)%mod;}
};
## 正文 ### day 0 没绷住确实是太烫了。 打信心赛，T1、T2、T3 都是宝宝题，T4 是 CF*3500。 最后变成手速场了，T4 完全不可做，**赛后大家发现 T4 写的乱搞都被 corner cases 卡完了**。 ## day 1 上午在打摆。 中午的时候感觉发烧了，睡了一会儿没睡着，感觉可能出问题。 进场之后先测了下速，注意到 `int` 进行 $1.5\times 10^8$ 次取模要用不低于一秒，没绷住直接笑出来了。 打了个缺省源，写了 `freopen` 和 `modint`，但是写挂了。 其实这个时候就已经注意到状态非常不好了，开了一包 QQ 糖，边吃边肉眼查错，调了两三分钟。 开题，T1 是调整法宝宝题，懒得思考了直接写了个 `priority_queue`，感觉非常稳，写完之后发现过不了编，看了下报错信息发现是 `freopen` 写错了。 T2 稍微想了一下暴力可以直接 $O(2^knk\alpha(n))$，换成状压 DP 能少一个 $k$，就直接开写。 写完了之后发现过不去大样例，调调调，发现有个 $\operatorname{lowbit}(i)$ 写成 $i$ 了，改了就过了。 不是哥们前两个题花了我一个半小时？？？我打锤子 CSP 呢。 继续看发现 T3 有个自然根号，脑袋一抽认为是 $n\sqrt{\sum len}$ 的，写了一发大样例 25s。 卡卡卡，卡了十多分钟卡到了 1s，去看 T4。 想了一会没啥思路就打了个阶乘暴力，调了好久发现 T4 题看错了，又看了会儿暴力瞪出了 $m=1$ 的性质：不合法当且仅当对于所有 $i$，都有 $c_i<i$，所以直接搞搞组合数就行了。 准备继续想的时候突然发现 T3 复杂度是 $\sum len\sqrt{\sum len}$ 的，那我过鸡毛啊直接跳了吧。有点慌了就没继续想 T4。 此时还有差不多 $110$ 分钟，然后最小丑的操作来了。 正常打的话应该直接去写 T3 的正解或者祈祷出题人不卡 T3 并直接 rush T4。 但我他妈是怎么干的？去 T3 给暴力卡常并且中途穿插思考 T4，这是人类干的事？？ 成功浪费了 $50$ 分钟后觉得 T3 没法继续卡了就思考 T4，然后 $10$ 分钟想到 $f_{i,j,k}$ 表示前 $i$ 天有 $j$ 个人没被录取，已经填了 $k$ 个 $>j$ 的数的方案数。 此时某人认为这是 $O(n^4)$ 的做法并试图优化，最后 $30$ 分钟写写写没调出来。 然后出场发现 T3 没判 $|t1|\neq |t2|$，荣升小丑，乱搞被 corner cases 二连击破了。 回家的时候稍微想了一下发现 T3 正解纯纯智障，之前 zhengrui 也碰到过类似的技巧但是我满脑子都是乱搞所以只写了乱搞。