题解 | #小苯的序列涂色#

小苯的序列涂色

问题分析

本题的核心在于如何以最小的代价通过染色操作（区间异或和）覆盖长度为 的整个序列。关键特征如下：

1. 区间重叠性：允许通过多个重叠的区间来覆盖同一位置。
2. 代价函数：区间 的代价为 。利用前缀异或和性质，令 （规定 ），则区间 的代价可表示为 。
3. 目标：将所有位置 染红。这意味着我们选择的区间集合 必须满足 。

通常的区间覆盖问题可以通过动态规划解决，但本题的代价函数是异或和，且允许重叠。如果仅考虑不重叠的划分，状态转移方程为 。但在允许重叠的情况下，例如 ，直接划分的最小代价是 ，而通过重叠区间 （代价 ）和 （代价 ）覆盖全段的代价仅为 。

这表明，允许重叠实际上提供了一种“回退”机制：在覆盖到位置 后，我们可以无代价地回到任何已覆盖的点 ，再从 开始开启一个新的区间。

算法：最短路径建模

我们将问题转化为图论中的单源最短路径（SSSP）问题。

1. 构图

建立一个拥有 个节点（索引从 到 ）的图：

• 节点定义：节点 代表序列的前 个位置。
• 前进边（染色边）：从节点 向节点 （其中 ）连一条边，权值为 。这代表通过染色区间 将位置 覆盖。
• 回退边（覆盖属性边）：从节点 向节点 （其中 ）连一条权值为 的边。这代表如果位置 已经被覆盖，那么位置 自然也处于被覆盖状态，且不增加额外代价。

2. 最优化目标

求从节点 到节点 的最短路径长度。

3. 算法：Dijkstra

由于边权 且存在 权边，该图不存在负权环，非常适合使用 Dijkstra 算法。

• 规模分析：节点数 ，潜在边数 。
• 效率考量：对于 的稠密图，使用堆优化的 Dijkstra 复杂度为 ，即 ；而直接使用原始的 Dijkstra 更为高效且代码简洁。

复杂度分析

• 时间复杂度：
  • 前缀异或计算：。
  • Dijkstra 算法：外层循环 次选择最小距离节点，内层循环 次更新邻接点（前进边+回退边）。
  • 总复杂度为 。
• 空间复杂度：
  • 存储前缀异或数组 ：。
  • 最短路数组 dist 和访问标记数组 vis：。
  • 由于不需要显式建边（可以在松弛时枚举 ），空间复杂度仅为 。