← 返回题目列表

Codeforces · 2103/B

B. 二进制打字机

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

给你一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ 和一个带有两个按钮的打字机: 0 和 1。最初,您的手指位于按钮上 0。您可以进行以下两种操作:

  1. 按下手指当前所在的按钮。这将打印出按钮上的字符。
  2. 将手指移至另一个按钮。如果您的手指放在按钮上 0,将其移至按钮 1,反之亦然。

的 成本 二进制字符串的 被定义为键入整个字符串所需的最少操作数。

在输入之前,您最多可以反转$$$s$$$中的一个子串$$$^{\text{*}}$$$。更正式地说,您可以选择两个索引 $$$1\le l\le r\le n$$$,然后反转子字符串 $$$s_{l\ldots r}$$$,从而生成新字符串 $$$s_1s_2\ldots s_{l-1}s_rs_{r-1}\ldots s_ls_{r+1}\ldots s_n$$$。

你的任务是找到通过对 $$$s$$$ 执行最多一次子字符串反转而获得的所有字符串中的最小可能成本。

$$$^{\text{*}}$$$ 字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

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

每个测试用例的第二行包含一个二进制字符串 $$$s_1s_2\ldots s_n$$$ ($$$s_i = \mathtt{0}$$$ 或 $$$s_i = \mathtt{1}$$$) - 二进制字符串 $$$s$$$ 的字符。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出最多执行一次子串反转后字符串 $$$s$$$ 的最小成本。

示例

输入
复制

6
3
000
3
111
3
011
3
100
5
10101
19
1101010010011011100

输出
复制

3
4
4
4
8
29

注意

在第一个测试用例中,我们可以选择不反转任何子字符串。我们可以执行 3 次 $$$1$$$ 操作来输入 000.

在第二个测试用例中,我们可以选择不反转任何子字符串。我们可以执行 $$$2$$$ 操作将手指移动到按钮 1。然后,我们执行$$$1$$$操作3次来输入 111.

在第三个测试用例中,我们可以选择不反转任何子字符串。我们可以执行$$$1$$$操作来输入 0。然后,我们执行操作 $$$2$$$ 将手指移动到按钮 1。最后,我们执行两次 $$$1$$$ 操作来输入 11,得到最终的字符串 011 仅使用 $$$4$$$ 操作。

在第四个测试用例中,我们可以反转子字符串 $$$s_{1\ldots 3}$$$,得到字符串 001。我们可以执行两次 $$$1$$$ 操作来输入 00。然后我们执行$$$2$$$操作将手指移动到按钮 1。最后,我们执行一次$$$1$$$操作来输入 1,得到最终的字符串 001 仅使用 $$$4$$$ 操作。

在第五个测试用例中,我们可以反转子字符串 $$$s_{2\ldots 3}$$$,得到字符串 11001。字符串的成本是 $$$8$$$,因为我们可以执行以下操作序列:

  • 执行$$$2$$$操作将手指移至按钮 1.
  • 执行 $$$1$$$ 操作两次以键入 11.
  • 执行$$$2$$$操作将手指移至按钮 0.
  • 执行 $$$1$$$ 操作两次以键入 00.
  • 执行$$$2$$$操作将手指移至按钮 1.
  • 执行一次 $$$1$$$ 操作来输入 1.

在第六个测试用例中,我们可以反转子字符串 $$$s_{5\ldots 17}$$$,得到字符串 1101111011001001000。可以证明,输入二进制字符串所需的最少运算次数为$$$29$$$。