test0927

小超手123 · 2023-09-27 16:45:40 · 个人记录

初始之路

算法：简单动态规划

当我们选定一个额定功率时，显然必定是 a_i 中一个。

因此就可以将题目转换成分段问题。

记 f_{i,k} 表示将前 i 划分成 k 段的最小代价。

很明显 f_{i,k} = min(f_{j,k-1}+sum_{j,i}-mx\times(j-i+1))。

时间复杂度 O(n^2k)。

星锚

算法：二分+离散化+线段树

考场想出了正解，但写了一坨屎

subtask 1

考虑如何统计一个序列的连通块，可以在每个连通块的末尾统计，令连通块的末尾为 a_i，那么必定有 a_i \ge x > a_{i+1}，x 为当前的侵蚀力，每次暴力判断有多少个 i 满足该条件即可，时间复杂度 O(nm)。

subtask 2

换个角度来想，尝试直接统计每个侵蚀力的锚定次数，记 ans[x] 表示侵蚀力为 x 的答案。对于一个 a_i 和 a_{i+1}，把夹在它们之间的 ans[x] 加一即可。开棵线段树就能做到。注意到 a_i \le 10^9，开不了这么大，先离线把每个询问的值离散化下，然后二分查询需要修改的区间映射到离散化区间，具体的，对于每一个[L,R]，通过二分得到一个实际 [l,r]，在这个区间上进行线段树操作即可。

subtask 3

利用 subtask2 的思路，当你要修改一个世界泡的稳定性时，只需将原本这个世界泡带来的影响删掉，将更改后的世界泡的影响加上去就可以了。