2266C.md (1940B)
1 Source: https://codeforces.com/problemset/problem/2266/C 2 3 C. AND, OR, Sort! 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a binary string$^{\text{∗}}$ $s$ of length $n$. 22 23 You may perform the following operation any number of times (possibly zero): 24 25 * choose an integer $i$ ($1 \le i \le n$), and replace $s_i$ with either the [bitwise AND](https://en.wikipedia.org/wiki/Bitwise_operation#AND) or the [bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation#OR) of $s_1, s_2, \ldots, s_i$. 26 27 Note that the bitwise AND or bitwise OR of a single element is equal to the element itself. 28 29 Your goal is to make $s$ sorted in non-decreasing order$^{\text{†}}$. 30 31 Find the minimum number of operations required to sort $s$ in non-decreasing order. 32 33 $^{\text{∗}}$A binary string only contains characters $\texttt{0}$ and $\texttt{1}$. 34 35 $^{\text{†}}$If $s$ is in non-decreasing order, then $s_1 \leq s_2 \leq \ldots \leq s_n$. 36 37 Input 38 39 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 40 41 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the binary string $s$. 42 43 The second line of each test case contains the binary string $s$ of length $n$. Each character of $s$ is either 0 or 1. 44 45 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 46 47 Output 48 49 For each test case, print a single integer — the minimum number of operations required to sort $s$ in non-decreasing order. 50 51 Example 52 53 Input 54 55 ``` 56 6 57 58 4 59 60 0011 61 62 4 63 64 1000 65 66 5 67 68 01000 69 70 8 71 72 01001101 73 74 7 75 76 0101010 77 78 7 79 80 0111101 81 ``` 82 83 Output 84 85 ``` 86 0 87 88 3 89 90 1 91 92 2 93 94 3 95 96 1 97 ``` 98 99 Note 100 101 In the first test case, the string is already sorted, so no operations are required. 102 103 In the second test case, we can use bitwise OR to change the last three characters to 1, obtaining 1111 in $3$ operations.