Codeforces1437 B. Reverse Binary Strings

本文主要是介绍Codeforces1437 B. Reverse Binary Strings，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

You are given a string 𝑠 of even length 𝑛. String 𝑠 is binary, in other words, consists only of 0’s and 1’s.

String 𝑠 has exactly 𝑛2 zeroes and 𝑛2 ones (𝑛 is even).

In one operation you can reverse any substring of 𝑠. A substring of a string is a contiguous subsequence of that string.

What is the minimum number of operations you need to make string 𝑠 alternating? A string is alternating if 𝑠𝑖≠𝑠𝑖+1 for all 𝑖. There are two types of alternating strings in general: 01010101… or 10101010…

Input
The first line contains a single integer 𝑡 (1≤𝑡≤1000) — the number of test cases.

The first line of each test case contains a single integer 𝑛 (2≤𝑛≤105; 𝑛 is even) — the length of string 𝑠.

The second line of each test case contains a binary string 𝑠 of length 𝑛 (𝑠𝑖∈ {0, 1}). String 𝑠 has exactly 𝑛2 zeroes and 𝑛2 ones.

It’s guaranteed that the total sum of 𝑛 over test cases doesn’t exceed 105.

Output
For each test case, print the minimum number of operations to make 𝑠 alternating.

Example
inputCopy
3
2
10
4
0110
8
11101000
outputCopy
0
1
2
Note
In the first test case, string 10 is already alternating.

In the second test case, we can, for example, reverse the last two elements of 𝑠 and get: 0110 → 0101.

In the third test case, we can, for example, make the following two operations:

11101000 → 10101100;
10101100 → 10101010.

题意：
01序列，你可以翻转一段数使得0变成1，1变成0。
求翻转最少的段使得序列变成010101…或者101010…。

思路：
要是一个区间同时被翻转两次，那就等于没翻转，所以可以推出翻转的段一定是不交叉的。因此只需要枚举最终序列是1010，还是0101，然后算出要翻转多少段即可。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;typedef long long ll;
const int maxn = 2e5 + 7;int a[maxn];
int main() {int T;scanf("%d",&T);while(T--) {int n;scanf("%d",&n);int ans1 = 0,ans2 = 0;int flag = 0; //之前是否加过for(int i = 1;i <= n;i++) {scanf("%1d",&a[i]);if(a[i] != i % 2) {if(!flag) {ans1++;flag = 1;}} else {flag = 0;}}flag = 0;for(int i = 1;i <= n;i++) {if(a[i] != !(i % 2)) {if(!flag) {ans2++;flag = 1;}} else {flag = 0;}}printf("%d\n",min(ans1,ans2));}return 0;
}