AT_arc156_a [ARC156A] Non-Adjacent Flip

有 $N$ 枚编号为 $1$ 到 $N$ 的硬币，每枚硬币有正反两面，可以区分。硬币的正反面状态由一个长度为 $N$ 的字符串 $S$ 表示，$S$ 的第 $i$ 个字符为 `1` 时表示第 $i$ 枚硬币正面朝上，为 `0` 时表示反面朝上。 你可以进行如下操作，次数不限（可以为 $0$ 次）： - 选择满足 $1\leq i

输入通过标准输入给出，格式如下： > $T$ > $\mathrm{case}_1$ > $\vdots$ > $\mathrm{case}_T$ 每组数据格式如下： > $N$ $S$

输出共 $T$ 行。对于第 $i$ 个测试用例，如果可以通过操作将所有硬币都翻到反面，输出最小操作次数；否则输出 $-1$。

### 限制 - $1\leq T\leq 2\times 10^5$ - $3\leq N\leq 2\times 10^5$ - $S$ 是由 `0` 和 `1` 组成的长度为 $N$ 的字符串 - 输入的所有数均为整数 - 所有测试用例中 $N$ 的总和不超过 $2\times 10^5$ ### 样例解释 1 对于第 $1$ 个测试用例，选择 $(i, j)=(1, 3)$ 操作 $1$ 次即可将所有硬币翻到反面。对于第 $2$ 个测试用例，先选择 $(i, j)=(1, 3)$ 操作 $1$ 次，再选择 $(i, j)=(4, 6)$ 操作 $1$ 次，共需 $2$ 次操作。对于第 $3$ 个测试用例，无法将所有硬币翻到反面，应输出 $-1$。对于第 $4$ 个测试用例，所有硬币已是反面，无需操作。 由 ChatGPT 4.1 翻译