分数: 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.
对于第四个测试用例,硬币已经显示出尾巴,因此不需要任何操作。