← 返回题目列表

AtCoder · arc156_a

A. 非相邻翻转

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

我们有 N 硬币编号 1 to N 有两个可区分的侧面。一个字符串 S 代表币的当前状态。如果 i- 第一个字符 S is 1, 硬币 i 正在显示头像;如果该字符是 0, 硬币 i 显示尾巴。

您可以重复以下操作零次或多次。

  • 选择一对整数 (i,j) 这样 1\leq i < j\leq N 和 j-i\geq \bm{2}。翻转硬币 i 和硬币 j.

判断是否可以使所有的 N 硬币出现尾巴。如果可能的话,找出所需的最少操作次数。

你被给予 T 测试用例解决。

约束

  • 1 \leq T \leq 2\times 10^5
  • 3 \leq N \leq 2\times 10^5
  • S 是一个长度为 N 组成 0 和 1.
  • 输入中的所有数字均为整数。
  • 对于每个输入文件,总和 N 测试用例最多为 2\times 10^5.

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

​ 每个案例的格式如下:

N
S

输出

打印 T 行。的 i第行 (1\leq i \leq T) 应包含使所有硬币显示尾巴所需的最少操作数,并且 -1 否则。


示例输入 1

5
3
101
6
101101
5
11111
6
000000
30
111011100110101100101000000111

示例输出 1

1
2
-1
0
8

对于第一个测试用例,您可以执行以下操作 (i,j)=(1,3) 一次操作使所有硬币都显示出尾巴。

对于第二个测试用例,您可以执行以下操作 (i,j)=(1,3) 然后用 (i,j)=(4,6) 使所有硬币在两次操作中都显示出尾巴。

对于第三个测试用例,你可以证明没有办法让所有的硬币都显示尾巴,所以你应该打印 -1.

对于第四个测试用例,硬币已经显示出尾巴,因此不需要任何操作。