Codeforces Educational Round 153

比较简单的题目。

首先存在一个观点：一个位置至多只会被交换一次。因为交换两次的情况可以被某一种交换一次的方案替代。比如 \(101\) 进行 \((1,2),(1,3)\) 两次交换得到序列 \(110\)，可以使用一次交换 \((2,3)\) 达到相同的效果。

故我们知道：每个点的颜色最多只会反转一次。我们可以将异色位置对 \((i,j)\) 颜色的交换看成两个分立的过程：将 \(i\) 的颜色反转，将 \(j\) 的颜色反转。

考虑最后需要满足的条件：

反转的 \(0/1\) 个数相同。
\(10\) 子序列的数量变化量 \(\displaystyle =\frac{原串 1 的数量 \times 原串 0 的数量}{2}-原串 01 子序列数量\)。

设计 DP 状态 \(F_{i,j,k}\) 表示前 \(i\) 个位置，\(0\) 反转个数 \(-\) \(1\) 反转个数为 \(j\)，\(01\) 子序列变化量为 \(k\)。

转移时间复杂度为 \(O(n^4)\)。

考虑如下建图：每个间隙向左右建边；对于每种不同种类的空隙建立一个超级源点，并且向所有该种类的点建边。
那么对于每一种询问可能存在两种路径：

注意到空隙的种类数只有 \(26*26\) 种，枚举种类 \(T\)，从其超级源点 \(S_T\) 跑一次单元最短路。接下来检查所有询问经过 \(S_T\) 的情况：即使用种类 \(T\) 的跳转。

总时间复杂度为 \(O(n26^2)\)。