← 返回题目列表

Codeforces · 1971/D

D. 二值剪切

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

给你一个二进制字符串$$$^{\dagger}$$$。请找出需要将其切成的最小块数,以便将所得块重新排列成排序的二进制字符串。

请注意:

- 每个角色必须恰好位于其中一个棋子中;
- 这些片段必须是原始字符串的连续子串;
- 您必须使用重新排列中的所有棋子。

$$$^{\dagger}$$$ 二进制字符串是由字符 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$ 组成的字符串。排序的二进制字符串是这样的二进制字符串:所有字符 $$$\texttt{0}$$$ 都位于所有字符 $$$\texttt{1}$$$ 之前。

输入

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

每个测试用例的唯一行包含单个字符串 $$$s$$$ ($$$1 \leq |s| \leq 500$$$),由字符 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$ 组成,其中 $$$|s|$$$ 表示字符串 $$$s$$$ 的长度。

输出

对于每个测试用例,输出一个整数 - 能够将字符串重新排列成排序的二进制字符串所需的最小数量。

示例

输入 #1

6
11010
00000000
1
10
0001111
0110

输出 #1

3
1
1
2
1
2

注意

第一个测试用例如声明中所示。可以证明你不能使用少于 $$$3$$$ 的块。

在第二个和第三个测试用例中,二进制字符串已经排序,因此只需要 $$$1$$$ 块。

在第四个测试用例中,您需要在两个字符之间进行一次剪切并重新排列它们以形成字符串 $$$\texttt{01}$$$。