「训练日记」2024 年 4 月日记
点击查看目录
目录确实有必要写个东西监督自己 .
2024/04/01
感谢奇蛋物语让我理解为什么巨人被喷烂尾 .
Galaxy Union *2700
神金 .
如果不是一棵基环树可以直接换根 DP，是基环树导致的困难是，一些点对之间有两条路径，不知道走哪一条 .
不过如果以环为根，环上两个点子树内的点之间经过的环上路径和这两个点之间是一样的，考虑只处理换上的点之间的贡献，再给子树推下去 .
对于一个环上点 \(u\)，仅存在一个环上边 \((v1, v2)\) 使得 \(u\) 顺时针走到 \(v1\) 更优，逆时针走到 \(v2\) 更优，考虑每次移动当前枚举的点 \(u\) 时实时移动边 \((v1, v2)\)，感性理解下均摊是 \(O(n)\) 的 .
然后巨量细节就做完了 .
Gosha is hunting *3000
简记 wqs 二分 .
存在一种直接的 DP 是 \(O(n^3)\) 的，设 \(f_{i, a, b}\) 表示前 \(i\) 个数中选了 \(a\) 个一号球和 \(b\) 个二号球，瓶颈在于需要 \(a, b\) 选了多少个都要枚举 .
考虑能不能删掉一维，我们把所有 \((b, f_{n, a, b})\) 撒到一个坐标系上观察：
发现这是一个单调的凸函数，也就是说如果不限制 \(b\) 取多少个（状态改成 \(f_{i, a}\)），全取一定会更优 .
如果能使 \((B, f_{n, a, B})\) 成为最大值那么 \(f_{i, a}\) 自然就会选出来 \(B\) 个二号球，那么就需要构造对于二号球的额外贡献 .
构造二号球的额外贡献，就是每选一个二号球都会减去一次额外贡献，放在坐标系上相当于 \(x\) 坐标每加一，\(y\) 坐标都会减一个常数，发现就是斜率 . 也就是说，我们要构造一个斜率，使得该斜率下穿过这些点的直线中，穿过 \((B, f_{n, a, B})\) 的截距 \(b\) 最大（\(b = y - kx\)，即原 DP 值减去额外贡献）.
最后只需要思考如何求这个斜率了，发现凸函数的优秀之处在于，与一个凸函数相切的直线的斜率随相切的点的横坐标变大而变小，于是考虑二分这个斜率 .
这样就做到了 \(O(n^2\log n)\)，不过其实还可以把一号球也优化掉以达到 \(O(n\log^2 n)\) 的复杂度 .
Levels and Regions *2400
经典结论是，\(p_i\) 的概率通关期望时间为 \(\dfrac{1}{p_i}\)，那么 \(l\sim r\) 为一个级别时 \(r\) 通关的期望时间为 \(\dfrac{sumt_{r} - sumt_{l - 1}}{t_{r}}\) .
朴素 DP 是 \(f_{i, j}\) 表示第 \(i\) 个关卡为 \(j\) 级别的结尾，设 \(g_{i} = \sum_{j = 1}^{i}\dfrac{sum_{j}}{t_{j}}\)，\(h_{i} = \sum_{j = 1}^{i}\dfrac{1}{t_{j}}\)，有转移：
\[\begin{aligned} f_{i, j} &= \max_{k = 0}^{i - 1}\left\{\sum_{p = k + 1}^{i}\dfrac{sumt_{p} - sumt_{k}}{t_p} + f_{k, j - 1}\right\}\\ &= \max_{k = 0}^{i - 1}\left\{g_{i} - g_{k} - sumt_{k}(h_i - h_{k}) + f_{k, j - 1}\right\}\\ f_{k, j - 1} - g_{k} + sumt_{k}h_{k} &= sumt_{k}h_i + f_{i, j} - g_{i}\\ \end{aligned} \]是经典的斜率优化 .
太久不碰都不会形式化处理了唉 .
标签：训练,dfrac,sum,sumt,2024,斜率,日记 From： https://www.cnblogs.com/K8He/p/-/Diary-202404