2022/7/29 考试总结

时间安排

7:30~10:00

看到题之后，一眼就看出了T3的思路，可能也是之前做过类似的题，写之前还想了一会怎样能不分类讨论，为了不被卡精度还写了个分数类。好在写完没怎么调就过了大样例。
而且似乎大样例还挺强的。

10:00~10:40

T1可以写一个$O(n{m}^3)的dp$，因为转移时单调的，可以二分，复杂度为$O(n{m}^{2}logm)$，可以通过60pts，但是因为状态设计就是$n^3$的，因此不知道怎么优化。

10:40~12:30

一直在写交互，暴力直接连边然后拓扑。
链的部分分，一开始想写一个随机化的分治，但是发现次数有的时候会超。
于是改写为稳定的归并排序。

考后总结

T1

有两种优化思路：
1：$n\ge log2(m)$时，答案为$log2(m)$，因此复杂度可以直接降为$m^{2}lo{g}^{2}m$
而且考试的时候数据非常水，根本没有$n<log2(m)$的点，因此直接输出这个就可AC
2：发现如果区间长度固定，那么值是完全一样的，因此复杂度就可以进一步降为$mlo{g}^{2}m$
考试都时候，一直在想怎么加速dp，没有分析题目的性质，下次要注意。

T2

感觉和正解写的差不多，但是不知道为什么就是过不掉。
待upd