date: 2021.07.08 ??:??-??:??

practice link

题目大意：一场比赛有 $n$ 道题，每题有一定的分值。你和 tourist 两个人参加，每题只有先通过的人能得分。每次你和 tourist 分别选一道题做，如果你们做了同一道题，tourist 会比你先做完，你什么都得不到，然后继续抢剩下的题。如果你们选择了不同的题，你可以得到你选的那道题的分，但是之后 tourist 会开启暴走模式，秒掉剩下所有的题。问最优情况下你能得多少分。

题解：这是一个二人有限零和博弈。考虑状压 $dp$，显然当两个选择同一个问题时，收益是一个子问题，否则是你做的题的得分。考虑最小最大值定理，游戏的价值

$$ \begin{aligned} V&=\min_{\boldsymbol{q}\in Y^{*}}\max_{i=1}^{n}\sum_{j=1}^{n}a_{ij}q_{j}\\ &=\min_{\boldsymbol{q}\in Y^{*}}\max_{i=1}^{n}q_{i}b_{i}+(1-q_{i})a_{i}\\ &=\min_{\boldsymbol{q}\in Y^{*}}\max_{i=1}^{n}a_{i}+(b_{i}-a_{i})q_{i} \end{aligned} $$

单纯形的时间复杂度肯定是不过关的。考虑这样的判定问题：$\forall \boldsymbol{q}\in Y^{*},\max_{i=1}^{n}a_{i}+(b_{i}-a_{i})q_{i}\ge C$，即 $\forall\boldsymbol{q}^{*}\in Y^{*}\exists i\in\mathbb{N}\cap[1,n]a_{i}+(b_{i}-a_{i})q_{i}\ge C$。满足这样的判定问题的最大的 $C$ 即为答案。对于每个 $i$ 有

$$ \begin{cases} &q_{i}\le\frac{C-a_{i}}{b_{i}-a_{i}}&(b_{i}<a_{i})\\ &a_{i}\ge C&(b_{i}=a_{i})\\ &q_{i}\ge\frac{C-a_{i}}{b_{i}-a_{i}}&(b_{i}>a_{i}) \end{cases} $$

那么什么样的 $C$ 满足要求呢？对第二种情况，只要有一个 $a_{i}\ge C$，就满足要求。对于所有第三种情况，若所有右边都 $>0$，那么对于所有 $q$ 都 $=0$ 的情况就不一定有解。而只要有一个 $\le0$，即小于等于 $\max a_{i}$，那么显然有解，形式上和第二种情况一样。对第一种情况，显然要求右侧所有值和 $0$ 取 $\max$（这里很坑）的和加起来大于等于 $1$，求解时需要对 $a_{i}$ 排个序扫描线。综合这几种情况的 $C$ 的最大值，即为答案。