题目内容

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

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

题面描述

小苯有一个长度为 $n$ 的 $01$ 串 $x$（下标从 $1$ 到 $n$），格格有一个长度恰好为 $n-1$ 的 $01$ 串 $y$（下标从 $1$ 到 $n-1$）。要求在修改尽可能少的 $x$ 串字符后，使其满足以下匹配规则：

• 若 $y_i = 1$，则必须有 $x_i \neq x_{i+1}$；
• 若 $y_i = 0$，则必须有 $x_i = x_{i+1}$。

一次修改操作是选择一个位置 $i\,(1\le i\le n)$，令 $x_i := x_i \oplus 1$。求最少需要多少次修改才能使匹配成立。

问题本质分析