1-1 - FZSGBall's Blog

714 字

4 分钟

1-1

2026-04-17

算法

CF题解

/

算法

/

每日一题

题面#

Good Egg Galaxy — Koji Kondo, Super Mario Galaxy

Let $n$ be a positive integer. Mario has a binary string $^{\text{∗}}$ $s$ of length $n$ . In one move, he can choose any position $i$ ( $2 \leq i \leq n-1$ ) such that it’s between two 1’s, i.e., $s_{i-1} = s_{i+1} = \texttt{1}$ , and then set $s_i$ to either 0 or 1.

Mario can perform this operation as many times as he wants (possibly zero). What’s the minimum and maximum number of 1’s that can be in the resulting string?

$^{\text{∗}}$ A binary string is a string whose characters are either 0 or 1.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 500$ ). The description of the test cases follows.

The first line of each test case contains an integer $n$ ( $3 \leq n \leq 100$ ) — the length of the string.

The second line of each test case contains a string $s$ of length $n$ consisting of characters 0 or 1.

Output

For each test case, output two integers — the minimum and maximum number of 1’s in the resulting string after some number of moves.

思路#

这题的操作是：选中一个中间位置 $i$ ，要求左右都是 $1$ ，然后把 $s_i$ 改成 $0$ 或 $1$

核心要分开算 $\mathrm{max}$ 和 $\mathrm{min}$

1. 最大值 $\mathrm{max}$ #

要让 $1$ 尽量多，只需要考虑把可变的 $0$ 变成 $1$

一个位置能从 $0$ 变成 $1$ 的条件是它当前形态为 $\texttt{101}$ （即中间是 $0$ ，两边是 $1$ ）

因此：

先统计初始 $1$ 的数量 $\mathrm{c}$
再统计满足 $s_{i-1}=1,\ s_i=0,\ s_{i+1}=1$ 的位置数 $\mathrm{d}$
$\mathrm{max}=\mathrm{c}+\mathrm{d}$

线性扫描一遍即可

2. 最小值 $\mathrm{min}$ #

要让 $1$ 尽量少，需要做一些 $1 \to 0$ 的操作（中心在 $\texttt{111}$ ）

关键观察： $\texttt{00}$ 可以看成分隔符。把字符串按 $\texttt{00}$ 切成若干段后，每段可以独立计算最小贡献，再求和

WARNING
为什么按 00 分段？
因为题目要求的可以更改的地方是在两个1之间，而如果出现了00，这两个元素不满足任何更改的条件（相邻有0）

对每一段 $[l, r]$ ：

找到这段最左侧的 $1$ ： $\mathrm{first1}$
找到这段最右侧的 $1$ ： $\mathrm{last1}$
如果这段没有 $1$ ，贡献为 $0$ ；否则令这一段最少能保留的 $1$ 数量为：

\mathrm{len}=\mathrm{last1}-\mathrm{first1}+1

于是整题的最小值是所有分段贡献之和：

\left\lfloor \frac{\mathrm{len}}{2}\right\rfloor + 1

最后求出结果，输出

代码#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
int main() {
6
    int t;
7
    cin >> t;
8
    while (t --) {
9
        int n; string s;
10
        cin >> n >> s;
11
        int c = 0;
12
        for (char ch : s) {
13
            c += (ch == '1');
14
        }
15

16
        int mx = c;
17
        for (int i = 1; i + 1 < n; ++i) {
18
            if (s[i] == '0' && s[i - 1] == '1' && s[i + 1] == '1') {
19
                mx ++;
20
            }
21
        }
22

23
        int mn = 0;
24
        int i = 0;
25
        while (i < n) {
26
            int l = i;
27
            int r = i;
28

29
            while (r + 1 < n && !(s[r] == '0' && s[r + 1] == '0')) {
30
                r ++;
31
            }
32

33
            int first1 = -1, last1 = -1;
34
            for (int j = l; j <= r; j ++) {
35
                if (s[j] == '1') {
36
                    if (first1 == -1) first1 = j;
37
                    last1 = j;
38
                }
39
            }
40

41
            if (first1 != -1) {
42
                int len = last1 - first1 + 1;
43
                mn += len / 2 + 1;
44
            }
45

46
            i = r + 1;
47
        }
48

49
        cout << mn << ' ' << mx << '\n';
50
    }
51
}