codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2237D.md (3310B)


      1 Source: https://codeforces.com/problemset/problem/2237/D
      2 
      3 D. Fullmetal Bitchemist
      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 A binary string is a string consisting only of characters $0$ and $1$. The two characters $0$ and $1$ are called opposite values.
     22 
     23 Consider a binary string $t$. Let $|t|$ be the length of $t$. When $|t| \ge 2$, for every $1 \le i \lt |t|$, the characters $t_i$ and $t_{i+1}$ are adjacent.
     24 
     25 A binary string $t$ is called beautiful if it can be reduced to a string of length exactly $1$ by applying the following operation any number of times, possibly zero:
     26 
     27 * Choose two equal adjacent characters, remove both of them, and insert one character with the opposite value in their place.
     28 
     29 For example, the string $\mathtt{10001}$ can become $\mathtt{1101}$ by replacing the first adjacent pair $\mathtt{00}$ with $\mathtt{1}$. Then it can become $\mathtt{001}$, then $\mathtt{11}$, and finally $\mathtt{0}$. Therefore, $\mathtt{10001}$ is beautiful.
     30 
     31 On the other hand, $\mathtt{111}$ is not beautiful. After one operation, it becomes $\mathtt{01}$, and then no operation can be applied.
     32 
     33 You are given a binary string $s$. Compute the number of non-empty beautiful substrings$^{\text{∗}}$ of $s$.
     34 
     35 $^{\text{∗}}$A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
     36 
     37 Input
     38 
     39 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.
     40 
     41 The first line of each test case contains an integer $n$ ($1 \le n \le 10^6$) — the length of $s$.
     42 
     43 The second line of each test case contains a binary string $s$ of length $n$.
     44 
     45 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.
     46 
     47 Output
     48 
     49 For each test case, output a single integer — the number of beautiful substrings of $s$.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 10
     57 
     58 1
     59 
     60 0
     61 
     62 2
     63 
     64 01
     65 
     66 5
     67 
     68 01001
     69 
     70 3
     71 
     72 001
     73 
     74 6
     75 
     76 011110
     77 
     78 9
     79 
     80 010110110
     81 
     82 12
     83 
     84 010000101001
     85 
     86 16
     87 
     88 1010011010010110
     89 
     90 20
     91 
     92 11110101101101001110
     93 
     94 30
     95 
     96 000101100011111001111100000010
     97 ```
     98 
     99 Output
    100 
    101 ```
    102 1
    103 
    104 2
    105 
    106 10
    107 
    108 5
    109 
    110 15
    111 
    112 30
    113 
    114 47
    115 
    116 81
    117 
    118 139
    119 
    120 316
    121 ```
    122 
    123 Note
    124 
    125 In the first test case, the only non-empty substring is $\mathtt{0}$, which is already a binary string of length $1$. Therefore, it is beautiful.
    126 
    127 In the second test case, the beautiful substrings are $\mathtt{0}$ and $\mathtt{1}$. The substring $\mathtt{01}$ is not beautiful, because its two characters are not equal, so no operation can be applied.
    128 
    129 In the third test case, the beautiful substrings are:
    130 
    131 * $s[1,1]=\mathtt{0}$;
    132 * $s[2,2]=\mathtt{1}$;
    133 * $s[3,3]=\mathtt{0}$;
    134 * $s[4,4]=\mathtt{0}$;
    135 * $s[5,5]=\mathtt{1}$;
    136 * $s[3,4]=\mathtt{00}$, which can become $\mathtt{1}$;
    137 * $s[2,4]=\mathtt{100}$, which can become $\mathtt{11}$, then $\mathtt{0}$;
    138 * $s[3,5]=\mathtt{001}$, which can become $\mathtt{11}$, then $\mathtt{0}$;
    139 * $s[1,4]=\mathtt{0100}$, which can become $\mathtt{011}$, then $\mathtt{00}$, then $\mathtt{1}$;
    140 * $s[1,5]=\mathtt{01001}$, which can become $\mathtt{0111}$, then $\mathtt{001}$, then $\mathtt{11}$, and finally $\mathtt{0}$.
    141 
    142 Thus, there are $10$ beautiful substrings.