我觉得这场 CSP 还是太超模了

· · 生活·游记

吐槽一下 HB 神秘天气突然升温，赛时一直出汗，热了脱冷了穿反复横跳，可能影响了状态吧。

赛前打了很多模拟赛，但没有一场超过 150 分。

开场，看了 T1。

嗯，给定 n 个三元组，每个三元组可以选择其中一个元加入答案，但是不能有超过 n \over 2 个三元组选择同一个元。请最大化答案。

一眼看上去很像 DP，写出来但只有 55 分。40 min 左右看 T2。

我看看，给定一张图和另外 k 个特殊点，特殊点和原图中的每个点都有连边。每个特殊点可以花费一定代价激活，激活了才能使用。请求出所有情况下原图的 MST 最小值。\

当时我并没有太过于注意本题特殊的数据范围：n \le 10^4，m \le 10^6, k \le 10 。

写了一个 O(m \log m+2^k m) 的类朴素做法，但大样例跑得很快（关同步流 0.44 s），遂相信之。但大样例没开满。赛后听说这题卡常数，寄。

赛后我才注意到答案不会劣于原图的 MST，所以复杂度可以降为 O(m \log m + 2^k kn) 。

事后证明同学的这个做法过了。

遂回去苦战 T1。怀疑能不能贪。

注意到了 n \over 2 的限制，这表示如果直接贪心最多只会有一组超过限制，于是我考虑调整直接贪心的结果。当时我的想法是把代价小的放到次优的组，次优组不行再调第三组。写了 1.7k，2.5h 左右过了所有大样例。

感觉水平退化了，做黄还要这么久。

最后 1h 先写了 T4 8 pts 暴力。然后写 T3 。注意到去掉两个二元组中间的极长不同子段之后就成为了一个前后缀匹配问题，但是没有想到类似 AC 自动机的东西。赛后看到可以加入特殊字符然后多模式串匹配，然后就写出来了。

写了一个基于 hash 的暴力，结果 UBSan 查出来十几个神秘 UB。最后半个小时苦战 UB ，结果调完 UB 但 WA on replace3.in 。最后不出意料没有分。

最终结果：100 + 80 + 0 + 8 = 188 。

结论：游玩《矿产争霸》过多导致的。

证实了 送给好友的礼物 对于《矿产争霸》的评论。