CF-1437B Reverse Binary Strings 题解

题目大意

给你一个01字符串，你可以反转任意一个字符串子串，需要让这个字符串01交替，问最少需要反转多少次。

解题思路

这题不难，就是一道思维题。。

（思维真不行。。

因为需要所有0和1都不连续，所以可以统计连续的1和连续的0的数量。

每次反转最多同时使连续的1和0数量减一，所以答案就是连续的1和0中的最大值。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#define rep(i,a,n) for (ll i=a;i<=n;i++)
#define per(i,a,n) for (ll i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans *= a;
		a <<= 1, b >>= 1;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		string s; cin >> s;
		int cnt0 = 0,cnt1 = 0;
		for (int i = 1; i < s.length(); i++) {
			if (s[i] - '0' == 0 && s[i + 1] - '0' == 0)	cnt0++;
			if (s[i] - '0' == 1 && s[i + 1] - '0' == 1)	cnt1++;
		}
		cout << max(cnt0,cnt1) << endl;
	}
	return 0;
}