A15155. Tokitsukaze and Good 01-String (hard version)
编程题
普及/提高-
知识点
题目描述
This is the hard version of the problem. The only difference between the two versions is that the harder version asks additionally for a minimum number of subsegments.
Tokitsukaze has a binary string $s$ of length $n$ , consisting only of zeros and ones, $n$ is even.
Now Tokitsukaze divides $s$ into the minimum number of contiguous subsegments, and for each subsegment, all bits in each subsegment are the same. After that, $s$ is considered good if the lengths of all subsegments are even.
For example, if $s$ is "11001111", it will be divided into "11", "00" and "1111". Their lengths are $2$ , $2$ , $4$ respectively, which are all even numbers, so "11001111" is good. Another example, if $s$ is "1110011000", it will be divided into "111", "00", "11" and "000", and their lengths are $3$ , $2$ , $2$ , $3$ . Obviously, "1110011000" is not good.
Tokitsukaze wants to make $s$ good by changing the values of some positions in $s$ . Specifically, she can perform the operation any number of times: change the value of $s_i$ to '0' or '1' ( $1 \leq i \leq n$ ). Can you tell her the minimum number of operations to make $s$ good? Meanwhile, she also wants to know the minimum number of subsegments that $s$ can be divided into among all solutions with the minimum number of operations.
Tokitsukaze has a binary string $s$ of length $n$ , consisting only of zeros and ones, $n$ is even.
Now Tokitsukaze divides $s$ into the minimum number of contiguous subsegments, and for each subsegment, all bits in each subsegment are the same. After that, $s$ is considered good if the lengths of all subsegments are even.
For example, if $s$ is "11001111", it will be divided into "11", "00" and "1111". Their lengths are $2$ , $2$ , $4$ respectively, which are all even numbers, so "11001111" is good. Another example, if $s$ is "1110011000", it will be divided into "111", "00", "11" and "000", and their lengths are $3$ , $2$ , $2$ , $3$ . Obviously, "1110011000" is not good.
Tokitsukaze wants to make $s$ good by changing the values of some positions in $s$ . Specifically, she can perform the operation any number of times: change the value of $s_i$ to '0' or '1' ( $1 \leq i \leq n$ ). Can you tell her the minimum number of operations to make $s$ good? Meanwhile, she also wants to know the minimum number of subsegments that $s$ can be divided into among all solutions with the minimum number of operations.
输入格式
The first contains a single positive integer $t$ ( $1 \leq t \leq 10\,000$ ) — the number of test cases.
For each test case, the first line contains a single integer $n$ ( $2 \leq n \leq 2 \cdot 10^5$ ) — the length of $s$ , it is guaranteed that $n$ is even.
The second line contains a binary string $s$ of length $n$ , consisting only of zeros and ones.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
For each test case, the first line contains a single integer $n$ ( $2 \leq n \leq 2 \cdot 10^5$ ) — the length of $s$ , it is guaranteed that $n$ is even.
The second line contains a binary string $s$ of length $n$ , consisting only of zeros and ones.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
输出格式
For each test case, print a single line with two integers — the minimum number of operations to make $s$ good, and the minimum number of subsegments that $s$ can be divided into among all solutions with the minimum number of operations.
输入输出样例
输入 #1
5 10 1110011000 8 11001111 2 00 2 11 6 100110
输出 #1
3 2 0 3 0 1 0 1 3 1
说明/提示
In the first test case, one of the ways to make $s$ good is the following.
Change $s_3$ , $s_6$ and $s_7$ to '0', after that $s$ becomes "1100000000", it can be divided into "11" and "00000000", which lengths are $2$ and $8$ respectively, the number of subsegments of it is $2$ . There are other ways to operate $3$ times to make $s$ good, such as "1111110000", "1100001100", "1111001100", the number of subsegments of them are $2$ , $4$ , $4$ respectively. It's easy to find that the minimum number of subsegments among all solutions with the minimum number of operations is $2$ .
In the second, third and fourth test cases, $s$ is good initially, so no operation is required.
Change $s_3$ , $s_6$ and $s_7$ to '0', after that $s$ becomes "1100000000", it can be divided into "11" and "00000000", which lengths are $2$ and $8$ respectively, the number of subsegments of it is $2$ . There are other ways to operate $3$ times to make $s$ good, such as "1111110000", "1100001100", "1111001100", the number of subsegments of them are $2$ , $4$ , $4$ respectively. It's easy to find that the minimum number of subsegments among all solutions with the minimum number of operations is $2$ .
In the second, third and fourth test cases, $s$ is good initially, so no operation is required.