20251118 总结
starfallen · · 个人记录
T1
简单题，一眼猜出结论，画了
其实不算得到了正解，正解是建图后直接跑拓扑排序，而我直接找规律找出来了，代码甚至比正解要短。
T2
哈希神力。当时没想到正解就是哈希，算了一下复杂度发现哈希可以创，就直接一个双模哈希敲上去了。本来都交了，又测了一遍极限数据，发现 1.5s，然后卡常，成功使 70pts
正解竟然就是哈希，诡异。
T3
神人构造。首先我们观察到这道题的题面有以下特点。
- 构造题没有 checker。
- 提示：胆子大一点，不会
TLE的。 -
- 有无解情况但是不说输出什么（所幸样例中有这种情况，输出
-1）。
这就让我直接放弃了这道题。其实正解是一个 DP，但是我赛场上没想出来。好像搜索剪枝能拿不少分，但是我不会剪。好像高难度的搜索题我就不怎么会。等有时间了看看有没有那种纯搜索剪枝的高难度题做一做。
T4
线段树题。考场上成功想出正解的一半：70pts，然而没调完。
正解有一个神奇的做法。他发现矩阵记录状态是在是太过冗余了，于是利用这道题的性质，直接将矩阵优化成向量了，就一下子就把时空复杂度给降下来了。以后发现这种爆时间爆空间的算法可以考虑给信息降维。