CF2181M Medical Parity

护士米拉在一家过敏门诊工作。对每一位病人，米拉都按照固定顺序测试 $n$ 种过敏原。测试结果会被记录为一个长度为 $n$ 的二进制字符串 $x$ ：对于每一种过敏原，1 表示出现阳性反应，0 表示未出现反应。 为了分析反应的分布情况，米拉还会为 $x$ 记录一个奇偶校验控制字符串。对于一个长度为 $n$ 的二进制字符串 $x$，其奇偶校验控制字符串 $y$ 的定义如下：对于每一个位置 $i$（$1 \le i \le n$），令 $c_i$ 表示 $x$ 的前 $i$ 个字符（包括第 $i$ 个位置）中等于 1 的字符个数。奇偶校验控制字符串 $y$ 是一个长度为 $n$ 的二进制字符串，使得对于所有的 $i$（$1 \le i \le n$），都有 $y_i = c_i \bmod 2$。换句话说，如果 $c_i$ 是奇数则 $y_i$ 为 1，若为偶数则为 0。例如，若 $x=11101$，则 $y=10110$。 不幸的是，在记录数据时，测试结果字符串和校验字符串中的某些位可能被错误地记录。对于某个病人，米拉后来在系统中发现两个长度均为 $n$ 的二进制字符串 $x'$ 和 $y'$。它们原本应当分别是某个真实测试结果字符串 $x$ 以及其奇偶校验控制字符串 $y$，但在记录的过程中，$x$ 和 $y$ 的某些位可能被翻转了。例如，在上面的例子中，仅 $y$ 的第 3 位被翻转，得到了 $x'=11101$、$y'=10010$。 一次翻转操作是指选择两个字符串中的任意一位，将该位置的比特翻转（0 变为 1，1 变为 0）。米拉想要知道，记录这些数据时，可能发生的最少比特翻转次数是多少。 形式化地，给定两个长度为 $n$ 的二进制字符串 $x'$ 和 $y'$。你需要通过翻转 $x'$ 和 $y'$ 中的某些比特，将其变为 $x$ 和 $y$，使得 $y$ 是 $x$ 的奇偶校验控制字符串。请计算可能发生的最小总比特翻转次数。

输入第一行包含一个整数 $t$，表示测试用例的数量。接下来的 $2t$ 行，每两行为一个测试用例。每个测试用例的第一行是一个由 0 和 1 组成的非空二进制字符串 $x'$。接下来一行是与 $x'$ 长度相同的二进制字符串 $y'$。 所有输入中所有 $x'$ 字符串的总长度不超过 $10^6$。

输出 $t$ 行，每行一个整数，表示每个测试用例可能发生的最小比特翻转次数。

暂无提示。 由 ChatGPT 5 翻译