NOIP+？准省选难度？已经到了能力的边缘么？
但有点奇怪的是，这三道题的思考方向全部正确，T1 甚至只差临门一脚了；可惜部分分给得不那么让人舒服。
另外，这种“为了卡常而卡常”的时间限制着实令人不适；尤其是当 CWOI 的评测机本身配置落后的情况下。不过这也反过来使得我重新开始关注更底层的常数优化。
标签： 矩阵乘法加速递推
-
AtCoder ABC236G – Good Vertices – 题解 – 矩阵乘法优化DP
昨晚参与AtCoder ABC 236时认为G题似乎可做，直到看到数据范围才发现事情没有那么简单。
由于最近学习离线数据结构，又见识过一道题意接近的题目，故想到整体二分，二分每一个节点第一次能恰好经过$L$条边到达的时间，然后考虑DP求解。设计状态$f(i, x)$表示在该图上经过恰好$i$次转移能否到达点$x$。但很快发现每一次二分时均要重新在图上运行DP，时间复杂度无法承受。况且DP递推转移的次数$L$高达$10^9$，甚至不可能是线性的复杂度。
今天查看题解，发现有几个重要的，从未考虑过的trick：
- 既然要求能够经恰好$L$次转移到达的最早的时间点，则我们将每条边的边权$w$设为其加入图中的时间，则可以转化成恰有$L$条边的最小瓶颈路。
- 发现$L$很大，所以考虑通过矩阵乘法加速递推，也即所谓倍增优化DP的一种。