E

设 $f(i, 1/2/3/4)$ 表示走了 $k$ 步后与 $(x_2, y_2)$ 重合，横坐标相等，纵坐标相等，横纵坐标都不相等的方案数，递推即可。

F

很容易通过数据范围看出来是状压 DP。

可以规定先做第二种操作再做第一种操作。考虑 DP，设 $f(S)$ 表示 $S$ 中为 $1$ 的那些位从低到高依次对应 $b_1, b_2, \cdots, b_m$ 的最小代价，$k$ 为将 $i$ 交换到 $m + 1$ 所需要的次数，则有

$$ f(S \cup \{i\}) = \min_{i \not \in S}\{f(S) + |a_i - b_{m + 1}| \cdot X + kY\} $$

G

将所有点按 $b_i$ 升序排序，对于每个 $a_i$，可以求出对应的一个分界点 $k$，使得边权为

$$ w(i, j) = \begin{cases} a_i + b_j & j \le k \\ a_i + b_j - m & j > k \end{cases} $$

考虑 Dijkstra 的过程。对于当前点 $u$，先求出上面所说的分界点，前半部分用 $d_u + a_u + b_v$ 去更新，后半部分用 $d_u + a_u + b_v - m$ 去更新，这可以用线段树做到。

H

无聊的手玩题，感觉没有什么必要记。

Last modification：January 12, 2024
© Allow specification reprint
如果觉得我的文章对你有用，请随意赞赏