9月模拟赛总结

Leaper_lyc · 2024-09-10 10:12:19 · 个人记录

\tt 9.28 模拟赛总结

T1 打表找规律，找到一种做法（是正解），但是不会证明正确性，于是我前面的部分跑暴力，后面用那种做法，结果没考虑特殊情况，后面部分挂分了，所以只得到了暴力分。

T2 不会做，写了个暴力就跑了。

T3 曾今在某个小 OJ 的模拟赛上见过，当时我还订正了，所以会大致的做法，但是细节还是挺多的，所以花了挺长时间去调的。

T4 暴力调不出来，最终没能写完。

所以 就算是大样例过了，也不要轻信这道题过了，最好自己手动对拍。 还有就是今天 T1 最开始是不会做的，然后心态就开始崩裂了，直到想出做法后才恢复平常心，看来我还得多崩溃几次才能适应啊。

T1：很套路的贪心。

T2：凭借经验感觉是跟据特殊性质进行优化的那类 dp。于是先去写了 O(n^3) 的暴力。接下来转向研究 mex 的性质，发现一个正好跟转移有关的性质，简单证明了一下，于是写出了 O(n^2) 的做法，再加上前缀和优化就是正解。

T3：5 分钟左右想到前 50 分（暴力+特殊性质）。继续思考，想到一个树状数组直接统计的做法，发现假了。受“最大”和“最小”这两个词启发，联想到 Kruskal 重构树，这样子就可以用树状数组统计了，于是花了半个小时写+半个小时调。

插曲1：树状数组维护树上问题是我前几天板刷树状数组时学会的 trick，这次正好用上。

插曲2：这题交到9019上的时候 T 了 3 个点。发现是自己常数写大了（建立双向边，其实单向就可以）。

T4：打了前 20\% 的简单部分，然后就不会了，上次遇到这样的题也是只会暴力和特殊性质，无从下手。

不难发现这些分数都得益于多刷题，比如板刷树状数组的题单，以及上个月末专门做了一个 DP 的提升计划，上周主要是板刷联通性问题。而且，要想清楚细节后再开始写。

T1 水体。T2 经典套路。T3 简单树形 dp。T4 神仙思考方法，需要学习。

T4 是将任务的时间和位置 (x,y) 放到平面直角坐标系上，然后任务就变成了一段段有斜度有长度的线段。

然后将线段映射到 x 轴上，就变成了一段段与 x 轴平行的线段。最后用线段树维护。

转换方法很巧妙。