2024.10.22模拟赛反思

怎么感觉题目越简单打的越差啊？

\(T1\) 没什么好说的，\(8\) 分钟就做完了。

主要问题主要就是在 \(T2\) 上。其实本来 \(10 \min\) 就想到贪心怎么做了，但是发现直接贪心有点问题，所以就一直在想怎么解决。可能是前几场比赛考的比较难的缘故，我就一直在想能不能用数据结构进行维护，或者使用一些神奇方法规避这种问题，但是一直没想出来，最后只好打了一个暴力走人。其实正解就只需要在我的做法上加一个步骤，就是如果线段 \(A\) 包含线段 \(B\)，那就把线段 \(A\) 删去，最后就是一个普及组贪心。其实本质上还是想复杂了，而正解根本没有那么难。

后面两道题还算比较正常，该拿到的分都拿到了。\(T3\) 当 \(n \leq 100\) 时考虑容斥，先把中间元素互不相同的方案数求出来，然后再减去首尾相同但中间不同的方案数，其实可以直接把首尾集合合并起来，然后当做子问题去处理，这样时间复杂度就是 \(O(nm)\) 的。当 \(n > 100\) 时，此时最小的集合元素数量不超过 \(\frac{m}{n}\) 的，这样只需要枚举第一个集合选了哪个数，然后再进行 \(DP\)，最后尾部不选和首部相同的元素即可，这样单次时间复杂度 \(O(m)\)，总时间复杂度 \(O(\frac{m^2}{n})\)，可以通过。其实赛上想过容斥的，但是想的是另一种，导致就做不出来。

\(T4\) 拿了 \(n \leq 1000\) 和 \(a_i = 0\) 的 \(30\) 分，本来想写 \(60\) 分的树套树的，但是写的时候只剩 \(20 \min\) 了，遂放弃。正解是考虑把序列按照长度 \(k\) 分块，每块处理一个前缀李超树和后缀李超树，然后询问的时候最多查询两个区间，前面的区间是后缀，后面的区间是前缀，这样就可以 \(O(n \log n)\) 的时空通过了。

其实这场比赛主要就是反映了一个非常大的问题：

• 当一道题需要一些思考，但不需要太多时，由于难题做多的缘故，我可能就会绕进复杂的方法里面出不来，最后只好打暴力。但是事实上可能正解非常简单，在我的部分思考基础上再加一点点就能做出来。这应该是为什么我经常在简单场次爆炸的原因。其实像后面的两道题到是拿分拿的还行。

这个问题可能也比较好解决，就是当用比较高级的东西去做一道题做了很久都无果时，可以考虑往简单一点想，就比如这次 \(T2\) 有影响的区间我直接给他删了就行，这样应该可以避免在简单题上丢分。\(CSP-S\) 应该会比平常考试简单一点，希望在 \(CSP-S\) 时简单的题不要想的过于复杂，不然可能就会像今天一样把简单题的分丢了，到时候虽然有可能一等，但估计也是踩线，甚至都无法参加后续的活动。所以这个问题还是比较严重的，一定要规避。