b2
题目自己看
题解 ：
有贪心和dp两种思路
贪心的意思就是就近原则能变的区间尽量与旁边的区间保持一致
dp的思想就是以为两个数为一个小区间变或者是不变
f[]
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<cstring>
using namespace std;
const int N = 2 * 1e5 + 100;
typedef long long ll;
int n, m;
int a[N];
int b[N];
char s[N];
int f[N >> 1][2];
/*
f[i][2]
选到前i*2-1和i*2个的时候变成0和变成1所需要的段数
f[i][0]=min(f[i-1][1]+1,f[i-1][0]);
f[i][1]=min(f[i-1][0]+1,f[i-1][1]);
需要注意的是如果两个数相同不需要去改变它，而且需要与之前的01状态相比较
前面的状态有可能只能是一种状态，所以情况有点多。
*/
int main() {
int T;
cin >> T;
while (T--) {
scanf("%d%s", &n, s + 1);
memset(f, 0x3f, sizeof f);
int res = 0;
for (int i = 1; i <= n - 1; i += 2) {
if (s[i] != s[i + 1])res++;
}
if (res != 0) {
if (s[1] == s[2]) {
if (s[1] == '1') {
f[1][1] = 1;
} else {
f[1][0] = 1;
}
} else {
f[1][0] = 1;
f[1][1] = 1;
}
for (int i = 2; i <= n / 2; ++i) {
if (s[i * 2] != s[i * 2 - 1]) {
if (f[i - 1][1] >= 0x3f3f3f3f) {//前面只能为0
f[i][1] = f[i - 1][0] + 1;
f[i][0] = f[i - 1][0];
} else if (f[i - 1][0] >= 0x3f3f3f3f) {//唯一
f[i][1] = f[i - 1][1];
f[i][0] = f[i - 1][1] + 1;
} else {
f[i][0] = min(f[i - 1][1] + 1, f[i - 1][0]);
f[i][1] = min(f[i - 1][0] + 1, f[i - 1][1]);
}
} else {
if (s[2 * i] == '1') {
if (f[i - 1][0] >= 0x3f3f3f3f) { //只能为1
f[i][1] = f[i - 1][1];
} else if (f[i - 1][1] >= 0x3f3f3f3f) { //只能为0
f[i][1] = f[i - 1][0] + 1;
} else {
f[i][1] = min(f[i - 1][0] + 1, f[i - 1][1]);
}
} else {
if (f[i - 1][0] >= 0x3f3f3f3f) { //只能为1
f[i][0] = f[i - 1][1] + 1;
} else if (f[i - 1][1] >= 0x3f3f3f3f) { //只能为0
f[i][0] = f[i - 1][0];
} else {
f[i][0] = min(f[i - 1][1] + 1, f[i - 1][0]);
}
}
}
//printf("%d %d\n", f[i][0], f[i][1]);
}
int ans = min(f[n / 2][0], f[n / 2][1]);
cout << res << ' ' << ans << endl;
} else {
int f = 0;
char fi = s[1];
for (int i = 2; i <= n; i++) {
if (s[i] != fi) {
fi = s[i];
f++;
}
}
printf("%d %d\n", res, f + 1);
}
}
return 0;
}
