乘积
题目来源:ABC239 Task Ex (Dice Product 2)
Atcoder 链接:https://atcoder.jp/contests/abc239/tasks/abc239_h
设 fi 表示当前 M=i 的期望时间,则有 fi=1+1nn∑j=1fij。
此时我们发现,⌊mi⌋ 相同的 i,f 值一样。
所以我们可以设 gi 表示 M=1,m=i 的值。答案即为 gm。
则有 gi=1+1nn∑j=1g⌊ij⌋,记忆化搜索即可。
复杂度与杜教筛相同,为 ∫√m2(√x+√mx)dx=O(m34)。
守卫 2
题目来源:Romanian Master in Informatics 2021, Day 2, Task "Paths".
QOJ 链接:https://qoj.ac/problem/2812
引理 1. 守卫所选目的地均为叶子。
引理 2. k 次贪心选择使得答案增加尽可能多的叶子即可。
证明. 设第 i 次选择的叶子是 leafi,答案对应增加了 aleafi 到 leafi 的链;若最优解包含 leaf1,⋯,leafi−1 但不包含 leafi,
- 若最优解不包含 aleafi 到 leafi 的链,由定义知任意选择最优解所选叶子 y 换为 leafi 不劣;
- 否则找到最优解所选叶子 y 使得 y 与 leafi 的 LCA 深度最大,由定义知将 y 换为 leafi 不劣。证毕。
以 1 为根,设 downv 表示 v 子树内距离 v 最远的叶子,upv 表示 v 子树外距离 v 最远的叶子。
引理 3. 对于 r=1 的情况,设选择叶子 x 时答案对应增加 ax 到 x 的链,则 ax 即为最深的祖先 v 使得 downv≠x(若不存在则认为 v=r)
引理 4. 将根从 r 移向儿子 q 时,所有 ax 中仅有 upq 和 downq 的值会从 r 变为 q,其他均不变。
对 r 进行 DFS,维护每个叶子 x 对应的答案增量,支持多重集的单点修改和查询前 k 大值之和即可,时间复杂度 O(nlogn)。
下降
题目来源:JOISC 2020 Day2 T3 (Ruins 3) (第 19 回日本情報オリンピック 春季トレーニング合宿)
- 情報オリンピック日本委員会作 『第 19 回日本情報オリンピック 春季トレーニング合宿競技課題』 はクリエイティブ・コモンズ 表示-継承 4.0 国際ライセンスで提供されています.
- https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html
- https://loj.ac/p/3276
- https://qoj.ac/problem/3557
考虑 h→p 的过程。
初始时序列 B 全为 0。从 2n 到 1 考虑将 hi 加入序列 B,枚举 j 从 hi 到 1,若 Bj 为 0,则在这里填入 i。如果没有这样的位置,则其不在 p 中现身。否则令 pBi=i。
而这样,每个位置是否存活取决于 mex(B) 与 hi 的大小关系。
设 fi,j 表示 2n 到 i,mex=j+1 的方案数。答案为 f1,n。
为了转移方便,我们可以把高度相同的两个柱子看成不同的元素,最后除以 2n 即可。
若 i 没有在 p 中出现过,则 j≥hi,mex 不会改变。fi,j←cfi+1,j,其中 c 为可以放的数字个数,为 j− 之前放过的无效数字个数。这是由于 mex 是不降的。
若 i 出现过,且没有改变 mex,我们将它搁置,直到 mex 改变时统计。因为我们并没有记录除了 mex 之外的信息。fi,j←fi+1,j。
若 mex 改变了,考虑新的 mex=j+k,则考虑先选出 k−1 个在序列中出现过的位置,和 i 在 B 中构成了 (j,j+k]。之后再考虑他们的 h 值。要满足 ≤j+s 的数不得超过 s 个。否则就会有一个数走向 0,不在 p 中现身。
设这样的方案数为 gk ,则 gk 可以非常简单地预处理。
最后,hi 的取值为 [j,j+k],故乘 k+1。
故 \displaystyle f_{i, j+k}\leftarrow (k+1)\binom {c-j-1}{k-1}g_{k}f_{i+1, j}。
时间复杂度 \mathcal O(n^3)。