题解

思路

把每次第二类操作看成连接两个下标的一条边。一个最优方案中的这些边没有必要形成环：含环连通块的边数不少于点数，改为逐点执行第一类操作不会更差。因此，真正带来一次节省的连通块是一棵树：$k$ 个非零元素用 $k-1$ 次第二类操作清零。

树是二分图。设二分后的两侧元素和之差绝对值为 $D$。逐叶消元可得，该树可行当且仅当

两侧都必须非空。特别地，不能把空集或全集误当作一种二分。值为零的元素可以直接忽略：把它加入树不会增加节省次数。

问题转化为：把非零元素划分出尽量多个合法子集，每个合法子集使答案减少一。

做法

子任务 1

对每个集合枚举非空真子集作为二分图的一侧，按上述条件判断合法性；再做经典子集划分动态规划。复杂度为 $O(3^n)$。

子任务 2

判断一个集合时，把元素折半。枚举两半的子集和，将一半排序；对另一半的每个子集和二分寻找使 $|2S_1-S|\le k-1$ 的搭配，并排除空集与全集。随后仍做子集划分动态规划。

子任务 3

若合法集合 $T$ 包含另一个合法真子集 $U$，把 $T$ 当作一个连通块永远不优于只使用 $U$：两者都只节省一次操作，而 $U$ 占用元素更少。因此只需保留包含意义下极小的合法集合。

按掩码从小到大扫描。若当前掩码已经包含某个先前发现的极小合法集合，就无需再次判定；否则用折半搜索判定。发现新的极小合法集合后，枚举它的全部超集，把“使用该集合一次”的结果传播过去。最终状态记录最多能选多少个互不相交的合法集合。

复杂度

前两档的最坏时间复杂度为 $O(3^n)$。满分算法的折半判定总量受极小合法集合剪枝约束，单次判定为 $O(2^{k/2}\log 2^{k/2})$，超集传播总量为 $O(3^n)$ 的严格子集；在 $n\le20$ 范围内可通过。空间复杂度为 $O(2^n)$。

正确性说明

无环化说明最优方案只需考虑森林；每个非平凡树连通块恰好比逐点操作少一次。逐叶消元给出了树连通块合法性的充要条件，因此最大化互不相交合法集合数与最小化操作数等价。包含合法真子集的合法集合不会提供更大节省，删除它不影响最优值。超集传播枚举了所有极小合法集合的互不相交组合，所以最终答案等于非零元素数减去最大合法集合数。