Skip to content

【期望】P17498 [ICPC 2026 Wuhan I] Lottery 笔记 ​

设 fi 表示玩到第 i 轮时的期望。

fi=−c−k(i−1)+1n∑jmax(Aj,fi+1)

将 A 从小到大排序,可知一段前缀会取到 fi+1,剩下的后缀会取到 Aj,这个分界点可以二分找到,若 k>0,前缀最终会变为空,此时无需再继续递归,因此 O(nlog⁡n) 递推即可。

若 k=0,每一轮的代价都相等,可以进行无限轮,因此每一轮面对的情况都相等,则有

f=−c+1n∑jmax(Aj,f)

即

1n∑jmax(Aj,f)−f−c=0

当 f→f+1,左边增加 ≤1,右边增加 1,故方程具有单调性,二分 f 即可。

最近更新