题面#

Cordell manages a row of $n$ seats at the Scuola Comunale di Musica Piova where students are strictly forbidden from sitting next to each other.

You are given a binary string$^{\text{∗}}$ $s$, where $s_i = \mathtt{1}$ indicates that the $i$-th seat has been occupied by a student, and $s_i = \mathtt{0}$ indicates that it is free now. It is guaranteed that no two adjacent seats are occupied currently. Cordell needs to add more students until it is impossible to seat anyone else in the row. However, she wants to achieve this state with as few students as possible.

Your task is to calculate the minimum total number of students seated when it is impossible to seat anyone else in the row.

$^{\text{∗}}$A binary string is a string where each character is either $\mathtt{0}$ or $\mathtt{1}$.

Input

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

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of seats in the row.

The second line of each test case contains the binary string $s$ of length $n$ ($s_i \in \{\mathtt{0}, \mathtt{1}\}$). It is guaranteed that no two adjacent characters are both $\mathtt{1}$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the minimum total number of seated students.

思路#

代码#

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;
10
        string s;
11
        cin >> n >> s;
12

13
        s = '1' + s + '1';
14
        int ans = 0;
15
        int L = 0;
16
        for (int i = 1; i <= n; i ++) {
17
            if (s[i] == '0') {
18
                if (s[i - 1] == '1') L = i;
19
                if (s[i + 1] == '1') {
20
                    int len = i - L + 1;
21
                    int c = (L == 1) + (i == n);
22
                    ans += (len + c) / 3;
23
                }
24
            } else {
25
                ans ++;
26
            }
27
        }
28

29
        cout << ans << '\n';
30
    }
31
    return 0;
32
}*n*