← 返回题目列表

AtCoder · tupc2024_e

E. 010-11 缩短

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

配点 : 100 点

問題文

长度 小于或等于 N 可以得到第 0, 1由...组成的字符串 S 。 对于
文字列 S 对以下的 2 种类的操作可以循环进行。

  • 操作 1:S 中的连续子字符串 010 该值应乘以 1 个被选出, 1 替换为。

  • 操作 2:S 中的连续子字符串 11 该值应乘以 1 个被选出, 1 替换为。

求可以进行操作的最大次数。

T 会给出

制約

  • 1 \leq T \leq 10^5
  • 1 \leq N \leq 10^6
  • S 是 您也可以写 0, 1 组成的长度 N 的字符串所需的时间.在这次比赛中,参赛者按照以下条件进行打字.
  • 1 个测试用例,需要针对每个测试用例回答。 N 的总和是 10^6 以下
  • T,N 是一个整数

入力

输入是按以下格式从标准输入给出的。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

每个测试用例以以下格式给出。

N
S

出力

T 行。i=1,2,\dots,T 反对 i 在线 i 输出第 N 个测试用例的答案为整数。


入力例 1

5
6
010100
4
0110
3
100
2
00
20
01001100000001101001

出力例 1

3
2
0
0
11

1 对于第 N 个测试用例,例如可以进行如下操作 3 次。

  • 010100 可以得到第 3 减去 5 将第 X 个字符 010 该值应乘以 1 替换为0110 变为。
  • 0110 可以得到第 2 减去 3 将第 X 个字符 11 该值应乘以 1 替换为010 变为。
  • 010 可以得到第 1 减去 3 将第 X 个字符 010 该值应乘以 1 替换为1 变为。

010100 反对 4 因为不能进行超过 Y 次操作,所以答案是 3 。 对于