题目理解

我们有 $A+B+C+D+E$ 张卡片，初始状态为：

• 前 $A$ 张：I（正面）
• 接着 $B$ 张：O（反面）
• 接着 $C$ 张：I（正面）
• 接着 $D$ 张：O（反面）
• 最后 $E$ 张：I（正面）

目标：通过若干次翻转操作，使得所有卡片都变成 I（正面）。

每次操作 $[L_i, R_i]$ 会翻转区间内的所有卡片（I↔O）。

花费：操作 $[L, R]$ 的花费是 $R-L+1$ 秒。

关键观察

1. 问题转化

设总长度 $len = A+B+C+D+E$。

定义数组 $a[1..len]$，初始时：

• $a[i] = 0$ 表示位置 $i$ 是 I（正面）
• $a[i] = 1$ 表示位置 $i$ 是 O（反面）

那么初始时：

• $[1, A]$：$0$
• $[A+1, A+B]$：$1$
• $[A+B+1, A+B+C]$：$0$
• $[A+B+C+1, A+B+C+D]$：$1$
• $[A+B+C+D+1, len]$：$0$

目标：让所有 $a[i] = 0$。

操作 $[L, R]$ 相当于对区间内的所有值进行异或 $1$。

2. 差分思想

定义差分数组 $d$：

• $d[1] = a[1]$
• $d[i] = a[i] \oplus a[i-1]$ for $i \geq 2$
• $d[len+1] = a[len]$（边界）

那么：

• 初始时 $d$ 中 $1$ 的位置对应着 $a$ 中值变化的位置
• 目标：所有 $d[i] = 0$

一次操作 $[L, R]$ 会翻转 $a[L..R]$，这等价于：

• $d[L] \leftarrow d[L] \oplus 1$
• $d[R+1] \leftarrow d[R+1] \oplus 1$

花费：$R-L+1$

3. 问题重述

现在问题变成：

• 我们有 $d$ 数组，其中某些位置是 $1$，其他是 $0$
• 每次操作选择两个位置 $i < j$，花费 $j-i$ 将 $d[i]$ 和 $d[j]$ 翻转
• 目标：用最小总花费让所有 $d[i] = 0$

注意：由于每次翻转两个位置，$1$ 的个数必须是偶数才有解。

4. 图论建模

把每个 $d[i] = 1$ 的位置看作图中的一个节点。

操作 $[L, R]$ 可以看作连接节点 $L$ 和 $R+1$ 的一条边，边权为 $R-L+1$。

问题转化为：将节点两两配对，使得配对边的总权值最小。

1. 确定 $1$ 的位置

初始 $d$ 中 $1$ 的位置是：

• $A+1$（从 I→O）
• $A+B+1$（从 O→I）
• $A+B+C+1$（从 I→O）
• $A+B+C+D+1$（从 O→I）

所以有 $4$ 个位置：$p_1, p_2, p_3, p_4$。

2. 配对问题

我们需要将这 $4$ 个位置分成 $2$ 对，每对 $(x,y)$ 的花费是它们之间通过操作可达的最小代价。

对于一对位置 $(p_i, p_j)$，最小花费就是它们之间的最短路径长度（边权为操作花费）。

3. 最短路计算

以所有位置为节点，每个操作 $[L, R]$ 对应一条边：

• 从 $L$ 到 $R+1$，边权 $R-L+1$
• 从 $R+1$ 到 $L$，边权 $R-L+1$（无向图）

我们需要计算 $p_1, p_2, p_3, p_4$ 之间的两两最短路。

4. 动态规划配对

用 DP 状态 $mask$ 表示已经配对的节点集合，计算最小总花费。

优化

实际上，由于只有 $4$ 个关键点，我们可以：

1. 只计算这 $4$ 个点之间的最短路
2. 使用 Floyd-Warshall 算法计算所有点对最短路
3. 然后枚举所有配对方案

总结

这道题的关键在于：

1. 差分转化：将区间翻转转化为端点翻转
2. 图论建模：将操作视为图中的边
3. 最短路计算：计算关键点之间的最短距离
4. 配对优化：将问题转化为最小权完美匹配

通过巧妙的建模，我们将一个看似复杂的区间操作问题转化为了经典的最短路和匹配问题。