题目内容

小苯有一个长度为 $n$ 的 $01$ 串 $x$ (下标从 $1$ 到 $n$ )，巧合的是格格也有一个长度恰好为 $n-1$ 的 $01$ 串 $y$。(下标从 $1$ 到 $n-1$ )

据说，格格的字符串 $y$ 是用来匹配小苯的字符串 $x$ 的 ，具体来说：

• 如果 $y_i=1(1≤i≤n-1)$，则意味着必须有:$x_i ≠ x_{i+1}$。

题解

题面描述

给定一个长度为 $n$ 的 $01$ 串 $x$（下标从 $1$ 到 $n$），和另一个长度为 $n-1$ 的 $01$ 串 $y$（下标从 $1$ 到 $n-1$）。串 $y$ 用于约束串 $x$，具体规则如下：

• 如果 $y_i=1$（$1 \leq i \leq n-1$），则要求 $x_i \neq x_{i+1}$。
• 如果 $y_i=0$（$1 \leq i \leq n-1$），则要求 $x_i = x_{i+1}$。

初始的串 $x$ 可能不满足 $y$ 的要求，允许通过将 $x$ 中的某个字符取反（即执行 $x_i := x_i \oplus 1$）来修改。目标是修改尽可能少的字符，使得最终的 $x$ 串满足所有的约束条件。