QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: Kevin5307

Posted at: 2025-12-12 19:46:08

Last updated: 2025-12-12 19:46:24

Back to Problem

题解

对每个能量钦定一种/多种策略是异常困难的,首先我们先考虑消掉能量的限制。下面说明,不限制任何时刻非负,而仅限制能量的期望值不小于 $0$,问题的答案不受影响。

可以感性的理解这样一个策略:在最开始执行 $n$ 次操作并忽略具体任务而统统执行,这相当于给我们一个初始分数。那么对于期望不小于 $0$ 的策略,在整个过程中,能量小于 $0$,也就是累计抵扣能量达到 $O(n)$ 级别的概率是关于 $n$ 成指数的。而与此同时,这前 $n$ 次操作对最终期望的影响是关于 $n$ 成线性关系的。那么,由于 $O(n)$ 在渐进意义下小于 $O(\exp(n))$,这前 $n$ 次操作不会产生最终的影响。

那么我们现在只用求期望能量不小于 $0$ 的最优策略即可。


对于一个纯策略 $\sigma=(l,B,S)$,其中 $l$ 代表我们选择的剧情线,$B$ 代表 ban 位上的任务,$S$ 代表选中后会放弃不执行的任务,我们可以将 $\sigma$ 抽象化成 $(p(\sigma),e(\sigma))$,表示执行策略 $\sigma$ 期望的能量和点数。那么对于一个混合策略 $\{(\lambda_i,p_i,e_i)\}$,我们可以看做是一个拥有参数 $(\sum\lambda_ip_i,\sum\lambda_ie_i)$ 的纯策略。

那假设我们现在有一个纯策略集合 $T=\{\sigma_i\}$,可以达到的所有混合策略,其实就是将每个纯策略看成平面上一个点,所围成的凸包中的所有点。那回到原问题,我们实际上就是求出,在第一象限中(能量非负,点数显然非负),最大的 $y$ 坐标是多少。


我们考虑二分答案 $e$,然后将坐标轴平移 $e$,这时我们只需要知道凸包是否有一部分在第一象限。此时我们有两个观察:

  1. 存在的充要条件是,要么有一个纯策略在第一象限,要么有两个纯策略分别在第二、四象限,且他们连线在原点上方。
  2. 若存在一条过原点直线,满足每个纯策略都在该直线下方,则凸包一定不经过第一象限。

考虑去二分这条直线。每次对于每条剧情线,求出一个(如果有)在直线上方的纯策略,然后分类讨论:

  1. 有一个纯策略在第一象限。返回 $\texttt{true}$。
  2. 第二、四象限分别有至少一个纯策略。返回 $\texttt{true}$。
  3. 根本就没找到满足条件的纯策略。返回 $\texttt{false}$。
  4. 第二象限有,但是第四象限没有。将直线倾斜,使得第四象限中位于直线上的面积更大,继续二分。
  5. 第四象限有,但是第二象限没有。类似地,将直线向反方向倾斜,继续二分。

有了这两层二分,我们只要对于每条直线,每个剧情线都能求合法的纯策略即可。


对于一条直线的限制,实际上就是我们认为每单位能量和每单位点数都分别有一个单位价值。Ban 掉一个任务的价值贡献是 $0$,同时我们可以分别算出任务被选择和被跳过的贡献,则不 ban 某个任务的贡献就是两者取 $\max$,那么 ban 掉贡献最小的 $b$ 个中贡献为负数的即可。判断完存在性之后,判断所在象限也是简单的。


那么我们就做完了!时间复杂度 $O(\sum m\log^3)$。

Comments

No comments yet.