[ABC313F] Flip Machines
一种很新的折半/根号分治。
手玩一下可以证明一个机器集合 \(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}\)，根据两个集合的大小选择做法就可以了。