← 返回题目列表

Codeforces · 2062/A

A. 字符串

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

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$,由 $$$\mathtt{0}$$$ 和/或 $$$\mathtt{1}$$$ 组成。在一次操作中,您可以从 $$$s$$$ 中选择一个非空子序列 $$$t$$$,使得 $$$t$$$ 中的任何两个相邻字符都不相同。然后,翻转 $$$t$$$ 的每个字符($$$\mathtt{0}$$$ 变为 $$$\mathtt{1}$$$,$$$\mathtt{1}$$$ 变为 $$$\mathtt{0}$$$)。例如$$$s=\mathtt{\underline{0}0\underline{101}}$$$和$$$t=s_1s_3s_4s_5=\mathtt{0101}$$$,则运算后$$$s$$$变为$$$\mathtt{\underline{1}0\underline{010}}$$$。

计算将 $$$s$$$ 中的所有字符更改为 $$$\mathtt{0}$$$ 所需的最少运算次数。

回想一下,对于字符串 $$$s = s_1s_2\ldots s_n$$$,任何字符串 $$$t=s_{i_1}s_{i_2}\ldots s_{i_k}$$$ ($$$k\ge 1$$$) 其中 $$$1\leq i_1 < i_2 < \ldots <i_k\leq n$$$ 是 $$$s$$$ 的子序列。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 输入测试用例的数量。

每个测试用例的唯一行包含字符串 $$$s$$$ ($$$1\le |s|\le 50$$$),其中 $$$|s|$$$ 表示 $$$s$$$ 的长度。

输出

对于每个测试用例,输出将 $$$s$$$ 中的所有字符更改为 $$$\mathtt{0}$$$ 所需的最少操作数。

示例

输入 #1

5
1
000
1001
10101
01100101011101

输出 #1

1
0
2
3
8

注意

在第一个测试用例中,您可以翻转$$$s_1$$$。那么 $$$s$$$ 就变成了 $$$\mathtt{0}$$$,所以答案是 $$$1$$$。

在第四个测试用例中,可以依次执行以下三个操作:

1.翻转$$$s_1s_2s_3s_4s_5$$$。那么 $$$s$$$ 就变成了 $$$\mathtt{\underline{01010}}$$$。
2. 翻转$$$s_2s_3s_4$$$。那么 $$$s$$$ 就变成了 $$$\mathtt{0\underline{010}0}$$$。
3. 翻转$$$s_3$$$。那么 $$$s$$$ 就变成了 $$$\mathtt{00\underline{0}00}$$$。

可以看出,在少于 3 次操作中无法将 $$$s$$$ 中的所有字符更改为 $$$\mathtt{0}$$$,因此答案为 $$$3$$$。