2024.10.18模拟赛反思

感觉今天状态不太好，整个人比较恍惚。早自习我都不知道在干什么，考试的时候脑子里也是一团糨糊（晚上提前到 \(12\) 点睡觉，结果状态更差了）。

首先是 \(T1\)，开始我以为简单无向连通图的“简单”是指的仙人掌，所以想了一个点双的做法。写到一半发现做法复杂了，用最小生成树就行，而且点双的做法仅适合仙人掌，不适合一般无向图，所以就换了一个最小生成树。赛后证明简单无向连通图是指不存在重边、自环的无向图，还好写了最小生成树这个普适性比较广的做法，不然今天就爆完了。耗时 \(1 \operatorname{h}\) 多一点（这个题都能做一个多小时）。

然后是 \(T2\)，开始想了一个自己觉得很对的贪心做法（其实正解也可以说是贪心，只不过和这个不一样），就是找被覆盖次数最多的点加进答案里，然后将经过它的还没有被删除的路径删除。但是找与某个点相关联的路径不好找，而且赛后评测说明这个贪心是错的。我也不知道怎么了，树上的问题我居然没往 \(LCA\) 的方向想，想的时候一直在想贪心，从来没想过换过方向。正解主要依赖一个结论：选择的点一定是某些路径两端的 \(LCA\)。然后求出每条路径两端的 \(LCA\)，再把这些 \(LCA\) 按深度从大到小排序，最后如果一条路径还没有覆盖到，就把它的 \(LCA\) 标记一下就行了，可以使用树上差分，时间复杂度 \(O(n \log n)\)。

\(T3\) 本来应该是我比较擅长的东西，但是今天没做出来。而且最开始题意理解错了，导致暴力分没拿全，只拿到了 \(l_i = 1\) 的分（前面没看清楚这里就看清楚了）。正解比较简单，可以将问题离线，然后将右端点排序，问题就转化为了能不能在某段前缀选取一些区间满足 \(a_i \geq l_i\)，使得可以不超出范围地完全覆盖整段区间。这个东西用一颗线段树维护就行了，对于每个位置尽量选能覆盖到它的最大的 \(a_i\)，最后判线段树上 \([l_i,r_i]\) 这段区间的最小值是否等于 \(l_i\)。本来应该是一道比较简单的数据结构题，可是一直没往正确的方向上去想

\(T4\) 一看就不可做，直接就跳了。正解是对于各种情况进行一些分讨，比如说叶子和根的情况。这道题比较难，没做出来也比较正常。

总的来说，可能今天的状态确实不太良好，影响了一些发挥（考试的时候脑子里感觉空荡荡的）。但是问题不只有这一个，还有一些其他的问题：

• 一些有段时间没见过的套路感觉有所遗忘，\(T2\) 这种树上的东西在没有其他做法时应该往 \(LCA\) 想一下，还有 \(T3\) 这种在线不好处理的就可以尝试离线做法。这可能是长时间没做过这种题导致的，所以学的时候一定要学扎实，然后之后要进行一些及时的复习。
• 好像出现了一个很久都没出现过的问题，就是一个思路行不通的时候我也没有尝试换思路，就一直死磕（\(T2\) 表现得尤其严重，\(T3\) 也有一点）。这样是不行的，因为出题人指不定就会让正解比较非常规/某些思路完全做不出来，导致死磕半天大概率都没用。所以说当一个思路想了很久都没有进展时可以换一个思路再想，说不定就想出来了，大不了重新回头再想原来的思路，前提是每种思路在自己不确定是对的情况下都不能花太久。

希望以后都不要再出现这种比较低级的错误（看来其他错误比较高级）了，因为这有可能会让我在完全有可能做出来一道题的情况下只取得很低的分数。而且希望坚决不要把这些问题带到 \(CSP\) 考场上，不然就凭我这个分数感觉二等都悬。