nantf的博客

博客

Extra Public Round #1 题解

2022-04-06 16:00:03 By nantf

乘积

题目来源:ABC239 Task Ex (Dice Product 2)

Atcoder 链接:https://atcoder.jp/contests/abc239/tasks/abc239_h

fi 表示当前 M=i 的期望时间,则有 fi=1+1nnj=1fij

此时我们发现,mi 相同的 if 值一样。

所以我们可以设 gi 表示 M=1,m=i 的值。答案即为 gm

则有 gi=1+1nnj=1gij,记忆化搜索即可。

复杂度与杜教筛相同,为 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,答案对应增加了 aleafileafi 的链;若最优解包含 leaf1,,leafi1 但不包含 leafi

  • 若最优解不包含 aleafileafi 的链,由定义知任意选择最优解所选叶子 y 换为 leafi 不劣;
  • 否则找到最优解所选叶子 y 使得 yleafi 的 LCA 深度最大,由定义知将 y 换为 leafi 不劣。证毕。

1 为根,设 downv 表示 v 子树内距离 v 最远的叶子,upv 表示 v 子树外距离 v 最远的叶子。

引理 3. 对于 r=1 的情况,设选择叶子 x 时答案对应增加 axx 的链,则 ax 即为最深的祖先 v 使得 downvx(若不存在则认为 v=r

引理 4. 将根从 r 移向儿子 q 时,所有 ax 中仅有 upqdownq 的值会从 r 变为 q,其他均不变。

r 进行 DFS,维护每个叶子 x 对应的答案增量,支持多重集的单点修改和查询前 k 大值之和即可,时间复杂度 O(nlogn)

下降

题目来源:JOISC 2020 Day2 T3 (Ruins 3) (第 19 回日本情報オリンピック 春季トレーニング合宿)

考虑 hp 的过程。

初始时序列 B 全为 0。从 2n1 考虑将 hi 加入序列 B,枚举 jhi1,若 Bj0,则在这里填入 i。如果没有这样的位置,则其不在 p 中现身。否则令 pBi=i

而这样,每个位置是否存活取决于 mex(B)hi 的大小关系。

fi,j 表示 2nimex=j+1 的方案数。答案为 f1,n

为了转移方便,我们可以把高度相同的两个柱子看成不同的元素,最后除以 2n 即可。

i 没有在 p 中出现过,则 jhimex 不会改变。fi,jcfi+1,j,其中 c 为可以放的数字个数,为 j 之前放过的无效数字个数。这是由于 mex 是不降的。

i 出现过,且没有改变 mex,我们将它搁置,直到 mex 改变时统计。因为我们并没有记录除了 mex 之外的信息。fi,jfi+1,j

mex 改变了,考虑新的 mex=j+k,则考虑先选出 k1 个在序列中出现过的位置,和 iB 中构成了 (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)

Comments

No comments yet.

Post a comment

You can use @mike to mention the user mike.

If you wish to input the '@' character, please use @@