2276B.md (2249B)
1 Source: https://codeforces.com/problemset/problem/2276/B 2 3 B. Replace and Compress 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a string $s$ of length $n$ consisting of the characters 0 and/or 1. You need to perform exactly one operation consisting of two steps: 22 23 1. choose at most one character with index from $2$ to $n-1$ inclusive and replace it with the opposite one: 0 to 1 or 1 to 0. You may choose not to change any character. The first and the last characters of the string cannot be changed; 24 2. replace each maximal block of consecutive equal characters with one such character. 25 26 A block is called maximal if it cannot be extended to the left or to the right by adding the same character. For example, after the second step, the string 100111011 will become 10101. 27 28 Count the number of different strings that can be obtained after performing this operation. 29 30 Input 31 32 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 33 34 Each test case consists of one line containing a string $s$ ($3 \le |s| \le 3 \cdot 10^5$) consisting only of the characters 0 and 1. 35 36 Additional constraints on the input: 37 38 * the sum of the lengths of strings $s$ over all test cases does not exceed $3 \cdot 10^5$. 39 40 Output 41 42 For each test case, print one integer — the number of different strings that can be obtained after performing the operation. 43 44 Example 45 46 Input 47 48 ``` 49 7 50 51 001 52 53 000 54 55 010 56 57 00010 58 59 100111011 60 61 001011010 62 63 1111 64 ``` 65 66 Output 67 68 ``` 69 1 70 71 2 72 73 2 74 75 3 76 77 3 78 79 2 80 81 2 82 ``` 83 84 Note 85 86 In the first test case, you may choose not to change any character or replace the second character. Before compression, the resulting strings are 001 and 011, respectively. After compression, both strings become 01, so the answer is $1$. 87 88 In the fifth test case: 89 90 * if no character is changed, after compression we get 10101; 91 * if the second character is replaced, we get 110111011, and after compression — 10101; 92 * if the fifth character is replaced, we get 100101011, and after compression — 1010101; 93 * if the seventh character is replaced, we get 100111111, and after compression — 101. 94 95 In total, three different strings can be obtained: 101, 10101, and 1010101.