CF1392G Omkar and Pies

Omkar 有一个有 $k$ 个位置的馅饼盘（$2 \leq k \leq 20$）。盘子的每个位置上要么放着巧克力馅饼，要么放着南瓜馅饼。然而，Omkar 并不喜欢当前馅饼的排列方式，他有一个理想的排列顺序。 为了帮助 Omkar，$n$ 个精灵排成一行准备交换盘子里的馅饼。第 $j$ 个精灵可以交换盘子中第 $a_j$ 个和第 $b_j$ 个位置上的馅饼。 为了尽可能接近理想的排列，Omkar 可以选择一段连续的精灵子区间，然后从左到右依次让盘子经过这段精灵，每个精灵按顺序执行自己的交换操作。但由于精灵们很辛苦地排成了一行，他们要求 Omkar 选择的区间长度至少为 $m$（$1 \leq m \leq n$）。 形式化地说，Omkar 可以选择两个整数 $l$ 和 $r$，满足 $1 \leq l \leq r \leq n$ 且 $r - l + 1 \geq m$，然后依次执行第 $l$ 个到第 $r$ 个精灵的交换操作：先交换 $a_l$ 和 $b_l$，再交换 $a_{l+1}$ 和 $b_{l+1}$，直到交换 $a_r$ 和 $b_r$。 请你帮助 Omkar 选择一段精灵区间，使得最终盘子中与理想排列相同类型馅饼的位置数量最大。注意，Omkar 的想象力很丰富，初始排列和理想排列中每种馅饼的数量可能并不相同。

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq m \leq n \leq 10^6$，$2 \leq k \leq 20$），分别表示精灵的数量、最小区间长度和盘子上的位置数。 第二行和第三行各包含一个长度为 $k$ 的字符串，仅由 $0$ 和 $1$ 组成，分别表示初始排列和理想排列。第 $j$ 个字符为 $0$ 表示第 $j$ 个位置是巧克力馅饼，为 $1$ 表示是南瓜馅饼。两行中 $0$ 和 $1$ 的数量不一定相同。 接下来 $n$ 行，每行两个整数 $a_j$ 和 $b_j$（$1 \leq a_j, b_j \leq k$，$a_j \neq b_j$），表示第 $j$ 个精灵可以交换盘子中第 $a_j$ 和第 $b_j$ 个位置的馅饼。

输出两行。 第一行输出一个整数 $s$（$0 \leq s \leq k$），表示最终排列中与理想排列相同类型馅饼的位置数量的最大值。 第二行输出两个整数 $l$ 和 $r$，满足 $1 \leq l \leq r \leq n$ 且 $r - l + 1 \geq m$，表示 Omkar 应该让盘子经过的精灵区间 $l, l+1, \dots, r$，以获得 $s$ 个与理想排列相同的位置。 如果有多组答案，输出任意一组均可。

在第一个测试样例中，交换过程如下： - 交换 $1$ 和 $3$：11000 变为 01100 - 交换 $3$ 和 $5$：01100 变为 01001 - 交换 $4$ 和 $2$：01001 变为 00011 最终排列与理想排列 00011 完全相同，因此有 $5$ 个位置相同，这是最优的。 在第二个测试样例中，交换过程如下： - 交换 $1$ 和 $3$：11000 变为 01100 - 交换 $1$ 和 $5$：01100 变为 01100 - 交换 $4$ 和 $2$：01100 变为 00110 - 交换 $1$ 和 $5$：00110 变为 00110 最终排列与理想排列 00011 有 $3$ 个位置相同，分别是第 $1$、$2$ 和 $4$ 个位置。在本例中，区间 $(l, r) = (2, 3)$ 更优，但该区间长度为 $2$，不满足 $m = 3$ 的要求。 由 ChatGPT 4.1 翻译