20251118 总结

简单题，一眼猜出结论，画了 $eps$ 秒证明，并成功得到正解。

其实不算得到了正解，正解是建图后直接跑拓扑排序，而我直接找规律找出来了，代码甚至比正解要短。

哈希神力。当时没想到正解就是哈希，算了一下复杂度发现哈希可以创，就直接一个双模哈希敲上去了。本来都交了，又测了一遍极限数据，发现 1.5s，然后卡常，成功使 70pts $\to$ 100pts。

正解竟然就是哈希，诡异。

神人构造。首先我们观察到这道题的题面有以下特点。

这就让我直接放弃了这道题。其实正解是一个 DP，但是我赛场上没想出来。好像搜索剪枝能拿不少分，但是我不会剪。好像高难度的搜索题我就不怎么会。等有时间了看看有没有那种纯搜索剪枝的高难度题做一做。

线段树题。考场上成功想出正解的一半：70pts，然而没调完。

正解有一个神奇的做法。他发现矩阵记录状态是在是太过冗余了，于是利用这道题的性质，直接将矩阵优化成向量了，就一下子就把时空复杂度给降下来了。以后发现这种爆时间爆空间的算法可以考虑给信息降维。