A16507. 1-1
编程题
普及-
知识点
题目描述
[Good Egg Galaxy — Koji Kondo, Super Mario Galaxy ](https://www.youtube.com/watch?v=56TfZJoZxv8)
设 $n$ 为一个正整数。Mario 有一个长度为 $n$ 的二进制串 $s$。
每一步操作中，他可以选择任意一个位置 $i$（$2 \leq i \leq n-1$），该位置需要同时满足它的左右相邻位置都是 $1$，即 $s_{i-1} = s_{i+1} = 1$，然后将 $s_i$ 改为 $0$ 或 $1$。
Mario 可以进行任意次数（也可以一次都不做）上述操作。请你求出最终字符串中 $1$ 的最小个数和最大个数分别是多少？
注：二进制串是指所有字符都是 $0$ 或 $1$ 的字符串。
设 $n$ 为一个正整数。Mario 有一个长度为 $n$ 的二进制串 $s$。
每一步操作中，他可以选择任意一个位置 $i$（$2 \leq i \leq n-1$），该位置需要同时满足它的左右相邻位置都是 $1$，即 $s_{i-1} = s_{i+1} = 1$，然后将 $s_i$ 改为 $0$ 或 $1$。
Mario 可以进行任意次数（也可以一次都不做）上述操作。请你求出最终字符串中 $1$ 的最小个数和最大个数分别是多少？
注：二进制串是指所有字符都是 $0$ 或 $1$ 的字符串。
输入格式
每组测试数据包含多个测试用例。第一行输入一个整数 $t$（$1 \leq t \leq 500$），表示测试用例数量。
每个测试用例的第一行输入一个整数 $n$（$3 \leq n \leq 100$），表示字符串的长度。
每个测试用例的第二行输入一个长度为 $n$ 的二进制串 $s$。
每个测试用例的第一行输入一个整数 $n$（$3 \leq n \leq 100$），表示字符串的长度。
每个测试用例的第二行输入一个长度为 $n$ 的二进制串 $s$。
输出格式
对于每组测试用例，输出两个整数，表示经过任意次操作后，最终字符串中 $1$ 的最小和最大个数。
输入输出样例
输入 #1
4 3 111 6 011011 7 1011101 9 100101101
输出 #1
2 3 3 5 4 7 5 7
说明/提示
在第一个测试用例中，最终字符串中 $1$ 的最小个数为 $2$，可以按如下方式转换：
$$ \mathtt{1}\underline{\mathtt{1}}\mathtt{1} \to \mathtt{101} $$
最大个数为 $3$，即不进行任何操作。
在第二个测试用例中，最小个数为 $3$，转换过程如下：
$$ \mathtt{011}\underline{\mathtt{0}}\mathtt{11} \to \mathtt{01}\underline{\mathtt{1}}\mathtt{111} \to \mathtt{0101}\underline{\mathtt{1}}\mathtt{1} \to \mathtt{010101} $$
最大个数为 $5$，转换过程如下：
$$ \mathtt{011}\underline{\mathtt{0}}\mathtt{11} \to \mathtt{011111} $$
$$ \mathtt{1}\underline{\mathtt{1}}\mathtt{1} \to \mathtt{101} $$
最大个数为 $3$，即不进行任何操作。
在第二个测试用例中，最小个数为 $3$，转换过程如下：
$$ \mathtt{011}\underline{\mathtt{0}}\mathtt{11} \to \mathtt{01}\underline{\mathtt{1}}\mathtt{111} \to \mathtt{0101}\underline{\mathtt{1}}\mathtt{1} \to \mathtt{010101} $$
最大个数为 $5$，转换过程如下：
$$ \mathtt{011}\underline{\mathtt{0}}\mathtt{11} \to \mathtt{011111} $$