[ABC313F] Flip Machines

_jimmywang_ · 2023-08-07 10:52:34 · 题解

一种很新的折半/根号分治。

手玩一下可以证明一个机器集合 S 的期望，先把 S 中 x=y 的机器对应的卡片翻好面，对于剩下的机器，如果一张卡片被至少一个机器覆盖过（即 x=i 或 y=i），那么它的期望是 \dfrac{a+b}{2}，否则就是 a。

首先把 x_i=y_i 的机器处理掉，如果 a_{x_i}<b_{x_i}，那就直接交换。然后就可以不管这些东西了。毕竟再翻只会使期望变小。

现在只考虑 x\not =y 的机器。

将 a_i\ge b_i 的卡片记为集合 P，剩下的为 Q。覆盖一张卡的贡献是 \dfrac{b_i-a_i}{2}。

首先有一个观察：

• 覆盖 Q 中点优于覆盖 P 中点。

• 对于 x_i\in P,y_i\in P，这个机器永远不用。

• 对于 x_i\in Q,y_i\in Q，这个机器必然使用。（这里官方题解好像写错了）

下面将 x\in Q,y\in P 的机器交换 x,y，变为 x\in P,y\in Q。

接下来介绍两种做法：

1.

暴力枚举 P 中被覆盖的点的集合 S，因为覆盖 Q 中的点优于覆盖 P 中的点，所以所有 x\in S,y\in Q 的机器必选。

复杂度 O(m+2^{|P|}n)。

2.

进行 dp，记 dp[i][j] 为处理完 P 中前 i 个点，当前 Q 中选的集合为 j 时，P 中已选的点的最大值。

同上，可以预处理 P 中每个点作为机器的 x 时对应的 y 的集合，只要选了这个点，必然覆盖所有的 y。

然后 dp 完以后加上 j 中点的贡献就行了。

复杂度 O(m+2^{|Q|}n)。

我们发现 |P|+|Q|=n，因此 \min(|P|,|Q|)\le \dfrac{n}{2}，根据两个集合的大小选择做法就可以了。