QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: jiangly

Posted at: 2026-04-05 16:31:58

Last updated: 2026-04-05 16:32:02

Back to Problem

题解

观察:最优策略是,设当前的分数是 $s$,把猫的分数看成 $-s$,则如果剩下的卡牌分数平均值为正选择操作 A,否则选择操作 B。

证明:操作 A 的贡献就是剩下卡牌的分数平均值,所以为正时一定选择操作 A。而注意到剩余卡牌分数总和一定是单调递减的,所以如果当前是负数,以后也是负数,所以选择操作 B。

分数为 $0$ 的熊猫可以直接忽略。最终答案可以看成每一步期望的总和,也就是 $$ \sum_{i=0}^U\sum_{j=0}^T\frac{{U\choose i}{T\choose j}}{U+T+C\choose i+j}\frac{\max\{0,2(U-i)+(T-j)-C(2i+j)\}}{U+T+C-i-j} $$ 枚举当前选了 $i$ 个独角兽和 $j$ 个老虎,乘积的第一项是到达这个局面的概率,第二项是这个局面下一次操作的期望。

枚举 $i+j=s$,则可以解出有贡献的部分是 $i\le t$,需要快速计算形如 $f(s,t)=\sum_{i=0}^t {U\choose i}{T\choose s-i}$ 的求和。注意到有递推式 $f(s+1,t)=\frac{f(s,t)\cdot (U+T-s)-{U\choose t+1}{T\choose s-t}\cdot (t+1)}{s+1}$。考虑组合意义,也就是在 $U+T$ 个物品里面选 $s$ 个,其中前 $U$ 个物品中至多选 $t$ 个。递推式的含义是,在选 $s$ 个的方案中,任意选择一个没选的物品,这时有可能导致前 $U$ 个物品中选了 $t+1$ 个,去掉这种情况后,剩下的每种方案恰好被算了 $s+1$ 次。由于限制 $t$ 关于 $s$ 是单调递减的,因此可以快速维护。还要计算形如 $g(s,t)=\sum_{i=0}^t{U\choose i}{T\choose s-i}i=U\cdot \sum_{i=0}^{t-1}{U-1\choose i}{T\choose s-1-i}$,维护方法和 $f(s,t)$ 一致。时间复杂度 $O(U+T)$。

Comments

No comments yet.