AT_abc313_f [ABC313F] Flip Machines

题目描述

有 $N$ 张编号为 $1$ 到 $N$ 的卡片。每张卡片的正反两面分别写有整数，对于第 $i$ 张卡片，正面写有 $A_i$，反面写有 $B_i$。一开始，所有卡片都正面朝上。

现在有 $M$ 台机器，编号为 $1$ 到 $M$。第 $j$ 台机器关联两个 $1$ 到 $N$ 之间的整数 $X_j, Y_j$（可以相同）。每次启动第 $j$ 台机器时，有 $\frac{1}{2}$ 的概率将编号为 $X_j$ 的卡片翻面，剩下的 $\frac{1}{2}$ 的概率将编号为 $Y_j$ 的卡片翻面。每次启动的概率彼此独立。

现在，すぬけ君将依次进行以下操作：

1. 选择一个由 $1$ 到 $M$ 之间的整数构成的集合 $S$。
2. 按照编号从小到大的顺序，依次启动 $S$ 中编号的机器各一次。

请你求出，すぬけ君如何选择 $S$，才能使“所有操作结束后，各卡片当前朝上的面上的整数之和”的期望值最大，并输出这个最大期望值。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_N$ $B_N$
$X_1$ $Y_1$
$\vdots$
$X_M$ $Y_M$

输出格式

请输出答案。当你的输出与真值的绝对误差或相对误差不超过 $10^{-6}$ 时，将被判定为正确。

输入输出样例 #1

输入 #1

3 1
3 10
10 6
5 2
1 2

输出 #1

19.500000

输入输出样例 #2

输入 #2

1 3
5 100
1 1
1 1
1 1

输出 #2

100.000000

输入输出样例 #3

输入 #3

8 10
6918 9211
16 1868
3857 8537
3340 8506
6263 7940
1449 4593
5902 1932
310 6991
4 4
8 6
3 5
1 1
4 2
5 6
7 5
3 3
1 5
3 1

输出 #3

45945.000000

说明/提示

限制条件

• $1 \leq N \leq 40$
• $1 \leq M \leq 10^5$
• $1 \leq A_i, B_i \leq 10^4$
• $1 \leq X_j, Y_j \leq N$
• 输入均为整数

样例解释 1

如果选择 $S$ 为空集，则不会启动任何机器，此时“所有操作结束后各卡片当前朝上的面上的整数之和”的期望值为 $3+10+5=18$。如果选择 $S=\{1\}$，则启动机器 $1$，

• 若卡片 $X_1=1$ 被翻面，则和为 $10+10+5=25$；
• 若卡片 $Y_1=2$ 被翻面，则和为 $3+6+5=14$。
  因此期望值为 $\frac{25+14}{2}=19.5$。
  所以最大期望值为 $19.5$。

样例解释 2

可能存在多台机器拥有相同的 $(X_j, Y_j)$。

由 ChatGPT 4.1 翻译