2024集训第二周总结

先对每天的情况来总结一下。

\(2024.10.15\) \(T1\) 总共花了接近 \(1 \operatorname{h}\)，不过好在最后想到了正确的做法。\(T2\) 浪费的太多时间，看到 \(n,m \leq 1000\) 意识到不是搜索，所以在想 \(DP\)，但是想了很久都没想出来，最后发现 \(DP\) 和搜索没什么区别，都要把当前状态记录下来。\(T3\) 看到是计数题就感觉很难，没怎么看就跳过了，考完才发现是水题。\(T4\) 想的和正解完全不沾边，并且也浪费了大量时间。最后由于时间浪费过多导致暴力分也没打好，喜提倒一。这场比赛的最大败笔就是跳了 \(T3\)。

\(2024.10.18\) \(T1\) 最开始题意理解错了，以为简单无向连通图是指仙人掌，遂想了一个点双的做法，后面点双写到一半发现可以直接用最小生成树平替，并且普适性更强（还是不太确定简单无向连通图是什么），就写了最小生成树。\(T2\) 一直在想一种贪心做法，其实这个做法正确性也不显然（就是错的），还只能做到 \(O(n^2)\)，但是实在没想到最后的结论是标记一定会打在路径两端的 \(LCA\) 上，这样就可以按照 \(LCA\) 的深度从大到小排序，然后用树状数组维护标记点即可。\(T3\) 脑抽了，只想到了 \(DP\)，而且题意理解错了，导致前 \(30 pts\) 没拿到，正解是把询问离线下来，然后用一颗线段树维护（感觉太久没做这种题有点生疏了）。\(T4\) 赛上没想到，正解是大力分讨。

\(2024.10.19\) \(T1\) 树形 \(DP\) 和二分答案都想过，但是觉得他们两个结合起来和直接 \(DP\) 没什么区别，就直接写了个 \(DP\)，在随机数据下答案大都是对的。正解就是先二分答案，然后在树形 \(DP\) 合并两条链的时候判一下两条链的边权和是否 \(\leq mid\)，这样就可以准确无误的得出答案，时间复杂度 \(O(nk \log V)\)（这种树上背包时间复杂度是 \(O(nk)\) 的）。\(T2\) 赛时根本没想到二分图（关于二分图模型我好像就只会炮塔模型，这种互相攻击的我还是第一次见），虽然没想到正确做法，但其实也没花太多时间（主要还是 \(T1\) 做得比较久），正解就是对于每个車的行和列连边，然后在上面跑一个匹配就行了。\(T3\) 看到数据范围感觉是状压 \(DP\)，但是没想出来，而且感觉暴力也不太好写，就直接信仰输出 \(n\)（直接保龄）。正解是可以先用 \(O(n m^3)\) 的时间复杂度去预处理，然后用 \(O(m^3 2^m)\) 去 \(DP\)，然后有两种方法可以将时间复杂度做到 \(O(m^2(n+2^m))\)，这样就能通过。\(T4\) 看到修改询问的东西、数据范围、时间限制就知道是分块，但是没想出来怎么分，最后打了一个 \(O(qn)\) 的暴力。正解就是先分块，然后为了使算法复杂度不带 \(\log\) 可以再次使用分块来平衡复杂度。

感觉这周其实暴露了很多问题：

• 有时候看到题目类型/数据范围就会给题目下主观的难度定义（如计数、构造），但是可能最后那些还比较可做的题往往就是这些自己看题面觉得很难的题（如 \(2024.10.15 \space T3\)）。以后还是要先对每个题都有一些大致的思考后再给题目下比较客观的定义。
• 卡题太久了一定要换。死磕一道题太久不仅会浪费大量时间，还会影响心态，导致有可能整场比赛就因为一道题卡住了就直接崩盘了。
• 感觉一些做题技巧有一些遗忘，一些及比较套路的题有点忘了怎么做。以后要注意温习之前所学的知识。
• 模型转化能力比较弱（如 \(2024.10.19 \space T2\)），

以后要注意保持一个良好的策略，对题目难度/耗时有客观评价，多做题，见识一些套路/通用方法，并且不要再犯上文中总结出来的问题。