标签：2w 函数 Alice ge GD230531B Bob 猜测 dp

GD230531B. 猜测

Alice 和 Bob 又在玩游戏。天天玩，玩不死你

给你 \(n\) 个数，\(n\le 10^7\)，数字离散化之后，Alice 每次选取值域相等或相邻的两个数，分别放到 Bob 的左右手，Bob可以选择看左手或者看右手，问最优策略下，不管 Alice 怎么选，Bob 的获胜概率最少为多少。

首先左手右手本质是一样的，Bob 应该选择各一半的概率看左右手。当然不能一定看某一个手，因为 Alice 不是随机选择的，所以如果 Alice 故意把不好猜的放到你看的那只手你就完蛋了。

也就是说，我们要制定一个策略，\(f_{i,</=/>}\) 表示看到数字 \(i\) 后猜 \(</=/>\) 的概率。显然，\(f_{i,<}+f_{i,=}+f_{i,>}=1\)。

假如 Alice 选了两个一样的数（前提是这个数的个数 \(\ge 2\)），获胜概率为 \(f_{i,=}\)，否则若 Alice 选择了值为 \(i,i+1\) 的两个数字，获胜概率为 \(\frac{1}{2} f_{i,>}+\frac{1}{2} f_{i+1,<}\)，因为你有各一半的概率选到 \(i\) 或 \(i+1\)。

我们发现我们只关心每种数是否出现 \(\ge 2\) 次，定义 \(b_i=[cnt_i\ge 2]\)。

确定策略后，Bob 的最小获胜概率就是上面所有两种概率取最小值。假设这个值是 \(w\)。

50pts?的做法

显然可以二分答案 \(w\)。然后根据不等式：

• \([b_i] f_{i,=}\ge w\)
• \(\frac{1}{2} f_{i-1,>}+\frac{1}{2} f_{i,<}\ge w\)
• \(0\le f_{i,j\in\{<,=,>\}} \le 1\)

首先我们知道 \(f_{1,<}=0\)，那么可以推出 \(f_{1,>}=1-[b_1]f_{1,=}\)。因为 \(f_{1,>}\) 对后面是有影响的，而 \(f_{1,=}\) 对后面没有影响，所以我们尽量把 \(f_{1,>}\) 取大，这样后面更可能成立，因此我们取 \(f_{1,=}=w[b_1]\)。

然后你又可以推出 \(f_{2,<}\) 的取值范围了，即 \(f_{2,<}\ge max(0,2w-f_{1,>})\)。然后由 \(f_{2,>}=1-f_{2,<}-f_{2,=}\)，显然 \(f_{2,>}\le 1\)，所以我们要让 \(f_{2,>}\ge 0\)，就要使它的取值范围尽可能的大。因此 \(f_{2,<},f_{2,=}\) 都要尽可能的小。因此 \(f_{2,<}=max(0,2w-f_{1,>}),f_{2,=}=w[b_2]\)，则 \(f_{2,>}=1-max(0,2w-f_{1,>})-w[b_2]\)。

把这个柿子单独拎出来：

\[dp_i=1-max(0,2w-dp_{i-1})-w[b_i] \]

其中 \(dp_1=1-w[b_1]\)。

要满足 \(\forall i , dp_i\ge 0\)。

二分答案可以做到 \(n\log n\)。但是是实数范围的答案。

据说可以枚举分子分母蒙一个分数逼近这个实数，据说可以过，我没试过。

满分做法

显然我们不能二分了。

看回那个柿子：

\[dp_i=1-max(0,2w-dp_{i-1})-w[b_i] \]

如果我们把 \(dp_{i-1}\) 看成已知函数，那么 \(dp_i\) 就是关于 \(w\) 的函数。求所有 \(dp_i\ge 0\) 的 \(w\) 的最大值。

显然这是一个分段函数，以 \(2w=dp_{i-1}\) 为断点。

• \(2w\le dp_{i-1},dp_i=1-w[b_i]\)
• \(2w> dp_{i-1},dp_i=-2w+dp_{i-1}+1-w[b_i]\)

前面一段很好想象，后面一段相当于是函数 \(dp_{i-1}\) 减去函数 \(2w\) 和 \([b_i]w-1\)

然后构造完这个函数我们要求它和 \(x\) 轴的交点，取满足 \(dp_i\ge 0\)，限制 \(w\) 的范围。

可以发现这个函数是这样的，在分界点之前只有一条直线，在分界点之后可以由函数 \(dp_{i-1}\) 先整体加上 \(-[b_i]w+1\)，然后这个东西和函数 \(y=2w\) 的交点就是答案 \(w\) 的范围。求完这个交点之后，交点后面那一坨 \(dp_i\) 都是 \(<0\) 的了，可以直接舍弃。

这玩意分这么多段，怎么求交点呢？

我们发现，每次转移，断点左边的斜率为 \(-b_i\)，而断点右边的斜率会整体减去一个 \(b_i\)，所以每次转移都是左边一部分变成斜率为 \(-b_i\)，右边进行后缀减，可以打 tag 保证时间，因此，整个函数将会是一个斜率递减的右上凸包（疑似这个凸包不密封？）。因此，以上提到的所有交点至多有一个。

求断点时，从左边枚举，把不合法的踢出去，然后新建一条线段。求答案范围时，从右边开始枚举，不合法的踢出。

时间是均摊线性的。

标签：2w,函数,Alice,ge,GD230531B,Bob,猜测,dp
From： https://www.cnblogs.com/liyixin0514/p/18418838