「晚测反思」2020-11-28 复盘

每场都考炸,不过每场都有值得复盘的地方

这场状态原因居多吧,手冷,敲不动键盘,裸的单调性没看出来,码速还是不太行

比较弱智的一场

因为写得慢就连 (T1) 暴力都没想,也没写

后来发现T1树上堆维护真的老套路了,(T2) 确实是想得不太周全了

T1

手玩样例大概可以观察最优策略,就是考虑让走大点的时候另一个点的权值尽量小

那么对于每个树维护一个堆,堆里面存储能到达的点

每次找一个堆里面的最小值来做另一个里面小于当前答案的最浅祖先

然后在另一个树里面拓展

中间对所有的已知点的和的 $ min$ 取 (max)

T2

折半维护,这部分复杂度是 (O(2sqrt {2^n}))

然后考虑对于 (a_i) 找到两个界点,考虑维护距离即可

那么发现随着 (a_i) 的上升,界点下降,所以双指针扫

还需要在每个找之前二分出来一个左边的 (a_1)

其实除了单调性以外的其它卡法都想到了……


其实确实都不是复杂题目……是自己状态的问题

原文地址:https://www.cnblogs.com/yspm/p/14056608.html