CSP-S2025

shiruoyu114514 · 2025-11-02 20:02:14 · 个人记录

感觉真的很迷。前一天晚上梦见自己只把第一题过了，然后就开始胡最后三个题，最后一个题都没写，只有 100pts，造成了一定的心理阴影。

开场。

T1：我去一眼开不出来。是 DP 吗？感觉不太会啊。怎么办？\frac{n}{2} 的这个限制一定有玄机。考虑 a_{i,3}=0 的部分分：首先让所有人都选择最高的那一档，然后让超限的集合调一部分人到另外一档。发现最多只有一个人超限，直接选最高然后直接贪心调整就行了。

T2：这题一看就不可做，看看数据范围：k \le 10，容易想到直接使用 2^k 枚举改造哪些城市。首先把原图的最小生成树求出来，然后枚举 k，一共会有 nk 条边，每次暴力使用 Kruskal 可以求出来，时间复杂度 O(2^knk \alpha(n+k))。极限数据 1.4s。卡常半天没卡过去，此时 16:30。

看 T3。感觉挺会的，于是胡了一个做法，感觉能做，但是肉眼可见的麻烦。再看一眼 T4，感觉不太能做。于是剩下整场就丢再 T3 了。

中间写了个 T3 的暴力用来拍。写出来的正解过不了大样例 3，但是能过 4，于是考虑把暴力与正解拼一块，接下来就看命了。此时 18:21。

成功写出来 T4 O(n!) 暴力已经是 18:27 了。感觉有一个唐氏点能打。死手快打！结果没打完，最后 CE 了，暴力都没了。

总结：当你觉得一个题细节十分多，过程十分繁琐的时候，相信自己，一定开不出来。不要这么赌。不要相信奇迹。