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
无聊的手玩题,感觉没有什么必要记。
2 comments
想想你的文章写的特别好https://www.jiwenlaw.com/
叼茂SEO.bfbikes.com