题解

思路

闭合要求水平线段能分成总长度相等的正、负两组，竖直方向同理；横竖交替还要求 $h=v$。这些必要条件也是充分的。

做法

子任务 1：枚举子集

分别枚举水平、竖直线段子集，寻找总和的一半。复杂度为 $O(2^h+2^v)$。

子任务 2：普通背包

用布尔背包记录可达和及前驱，在 $O((h+v)S)$ 时间内恢复两个等和划分，其中 $S$ 是方向总长度。

子任务 3：bitset 背包

用

求可达和，并保留每个前缀的 bitset 以恢复方案。总和至多 $10^6$，可以通过。

得到 $X^+,X^-,Y^+,Y^-$ 后，若 $|X^+|\le|Y^+|$，把两组水平长度降序、两组竖直长度升序排列；每轮优先使用正向线段，耗尽后使用负向线段，依次走水平、竖直。否则交换横纵角色，并使用对称排序和行走顺序。前缀平均值性质保证各段折线位于相应边界的一侧，因而不会严格自交，最终两方向位移都为零。

复杂度

满分算法时间复杂度为 $O((h+v)S/64+(h+v)\log(h+v))$，空间复杂度为 $O((h+v)S/64)$。