← 返回题目列表

Codeforces · 1437/B

B. 反转二进制字符串

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

给你一个长度为 $$$n$$$ 的字符串 $$$s$$$。字符串 $$$s$$$ 是二进制的,换句话说,仅由 0 和 1 组成。

字符串 $$$s$$$ 恰好有 $$$\frac{n}{2}$$$ 零和 $$$\frac{n}{2}$$$ 个($$$n$$$ 是偶数)。

在一次操作中,您可以反转 $$$s$$$ 的任何子字符串。字符串的子字符串是该字符串的连续子序列。

使字符串$$$s$$$交替需要最少多少次操作?如果对于所有 $$$i$$$,$$$s_i \neq s_{i + 1}$$$ 则字符串是交替的。交替字符串一般有两种类型:01010101...或10101010...

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$;$$$n$$$ 是偶数)——字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ ($$$s_i \in$$$ {0, 1})。字符串 $$$s$$$ 恰好有 $$$\frac{n}{2}$$$ 零和 $$$\frac{n}{2}$$$ 。

保证测试用例$$$n$$$的总和不超过$$$10^5$$$。

输出

对于每个测试用例,打印使 $$$s$$$ 交替的最小操作数。

示例

输入 #1

3
2
10
4
0110
8
11101000

输出 #1

0
1
2

注意

在第一个测试用例中,字符串 10 已经是交替的。

在第二个测试用例中,例如,我们可以反转 $$$s$$$ 的最后两个元素并得到:0110 $$$\rightarrow$$$ 0101。

在第三个测试用例中,我们可以例如进行以下两个操作:

1. 11101000 $$$\rightarrow$$$ 10101100;
2. 10101100 $$$\rightarrow$$$ 10101010。