CSPS2025坠机记

· · 生活·游记

T1 瞪眼贪心但是怕被坑（曾经某个良心出题人模拟赛T1贪心挖坑导致全机房几乎全部趋势）于是多想了 10 min 进行确认。写了 10 min 过掉样例。

T2 瞪眼想到 Kruskal。注意到 k 很小考虑状压。时间复杂度有点超标所以想到沿用以前的状态选用的边降低时间复杂度压到 O(2^{k}n\log n)。有点常数希望不会被卡。本题用时 45 min。

T3 瞪眼想到 Trie 树但是想了 25 min 没有头绪，于是决定先看 T4。

T4 发现自己不记得以前怎么做排列 dp 计数的题了于是想了 15 min 果断放弃继续回来看 T3。

T3 又想了 20 min 想到把不同部分一样的放一起离线做，将左半部分插入 Trie 后对这棵 Trie 遍历同时对左半部分一样的右半部分进行修改查询操作，我的思路差不多是这样。

我决定着手实现 T3，由于怕被卡不想写哈希以及没有在 map 中用 vector 为第二关键字的经历，我决定再拿一棵 Trie 树，以中间不一样部分穿插在一起得到的字符串为关键字将每个操作（含查询） 插到这个 Trie 树上，然后遍历这个 Trie 树把处在同一个点上的操作一起做掉（见上一段）。但这给我造成了不小的麻烦。

实现共计花费 50 分钟，但是发现大样例 4 始终 RE 过不掉。我尝试将 T3 后来提到的那个 Trie 树开二倍点 5 \times 10^{6} \rightarrow 10^{7} 但是没有任何变化。我认为可能是递归栈限制严格被认为发生了溢出便撤销了更改决定就这样碰碰运气。此时距比赛结束还有约 50 min。

剩下的时间我几乎全部用于 T4 的暴力，打了个 O(n^{2}2^{n}) 的状压 dp 然后写了个 n=m 的解法但不太清楚正确性。最后的时间我尝试冲其他性质的测试点但是毫无头绪全部失败。

出考场之后我意识到一个问题。按照我的做法，由于查询和修改全部被塞入第二棵 Trie 树，所以要开二倍点是必要的。这下倒闭了直接送掉 40 分。前面的三个样例感觉很水不知道我的代码有没有其他问题，我也没有查清样例 4 RE 的原因（不像是数组越界也不像是递归栈溢出，完了），要是再挂整题就废掉了。

高一 CSP 考成这样多半是废了。NOIP 再炸就完蛋了。