Skip to content

【期望】20261004C 随机打乱 笔记 ​

等概率随机打乱 n 个二元组 (ai,bi)。维护一个整数集合 S,初始时 S 为空。处理二元组 (ai,bi) 时,检查 S 中是否存在一个数位于区间

[min(ai,bi),max(ai,bi)]

如果不存在,则将 ai 加入集合 S;如果存在,则什么也不做。求 |S| 的期望值。n≤3000,a,b 构成 2n 的排列。

考察 |S| 增长的过程。第一个加入的区间必然会加入一个点 x,发现之后所有包含 x 的区间都不会再有贡献,即被划分为了 [1,x) 和 (x,n] 的子问题,因此考虑 DP。设 fl,r 表示考虑子问题 [l,r] 的期望长度。那么只需要在 C={x∣[ax,bx]⊆[l,r]} 中选一个作为“分界点”,然后递归为子问题。

fl,r=1+1|C|∑mid∈Cfl,amid−1+famid+1,r

状态数 O(n2),转移 O(n),时间复杂度 O(n3)。

考虑优化,∑fl,amid−1 类似扫描线思想,随着 r 增大容易用变量维护,另一半同理,因此优化到 O(n2)。

最近更新