题目描述

难度分:$1800$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$长为$n$的字符串$s$，只包含0和1。

你需要修改$s$中的一些字符（只能修改成0或1），使得把$s$按照连续相同字符分割后，每一段的长度均为偶数。

例如11001111分割成11，00，1111，长度都是偶数。

输出两个数：
1. 最少要修改多少个字符。
2. 在修改次数最少的前提下，最少可以分割成多少段。

输入样例

5
10
1110011000
8
11001111
2
00
2
11
6
100110

输出样例

3 2
0 3
0 1
0 1
3 1

算法

动态规划

一看到计数和求最值我最先想到的就是DP，但是本题的DP还是蛮有难度的。为了降低思维难度，这里我使用记忆化搜索来实现DP。

状态定义

注意到并不关心每一段连续相同的长度具体是多少，只关心奇偶性。因此定义状态$f[i][cur][eor]$，表示$[1,i)$中以数字$cur$结尾，且最后一段连续的$cur$长度奇偶性为$eor$，用异或运算来维护。在此情况下，最后能得到的最小翻转次数，及其对应的最小连续段数。

$f[i][cur][eor]$需要保存两个属性，一个是翻转次数$flip$，另一个是最小段数$cnt$。

状态转移

当前数字$s[i]$存在两种情况：翻转与不翻转。但并不是两种操作都能做

1. 如果$s[i]=cur$，只有在$eor=0$的情况下才可以翻转$s[i]$，这时候表示从$s[i]$开启了一个新的段，如果$eor=1$，说明前面的那一个连续段长度为奇数，不合法。不翻转时，后继状态为$t_1=f[i+1][cur][eor \oplus 1]$。当$eor=0$时，当前位置可以翻转，后继状态为$t_2=f[i+1][1-cur][1]$。$t_2.flip+1 \lt t_1.flip$成立时，翻转更划算，更新$flip=t_2.flip+1$，$cnt=t_2.cnt$；$t_2.flip+1=t_1.flip$成立时，看看翻转和不翻转谁的段数更少，以此标准来更新$cnt$。
2. 如果$s[i] \neq cur$，这时候不翻转才是另起一个新的段，需要满足$eor=0$，否则前面就出现了一个长度为奇数的段，不合法。而翻转是可以的，后继状态为$t_1=f[i+1][cur][eor \oplus 1]$。在$eor=0$的情况下考虑不翻转，后继状态为$t_2=f[i+1][1-cur][1]$，接下来仍然按照$s[i]=cur$的情况来分析，同理可得状态转移。

最后确定递归的终止条件，$i \gt n$时终止递归过程。此时如果$eor=1$，那最后一段是奇数长度，不是个合法解，直接让$flip=cnt=\infty$。否则翻转次数$flip=0$，并且结算一段长度$cnt=1$。

本题我在实现时是调用$dfs(1,s[1],0)$，所以对于上述的情况$1$，在$i=1$的状态转移时需要做一个特判，避免多计算一段。

复杂度分析

时间复杂度

状态数量为$n \times 2 \times 2$，$DFS$函数中没有循环操作，单次转移的时间复杂度为$O(1)$级别，因此算法整体的时间复杂度为$O(n)$。

空间复杂度

空间消耗的瓶颈就是DP数组，它的规模就是状态数量，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010, INF = 0x3f3f3f3f;
int n;

struct Info {
    int flip, cnt;
} f[N][2][2];
char s[N];

// [1,i)中以cur结尾，并且最后cur个数的奇偶性为eor
Info dfs(int i, int cur, int eor) {
    if(i > n) {
        if(eor == 0) {
            f[i][cur][eor].flip = 0;
            f[i][cur][eor].cnt = 1;
        }else {
            f[i][cur][eor].flip = f[i][cur][eor].cnt = INF;
        }
        return f[i][cur][eor];
    }
    if(f[i][cur][eor].flip != -1) {
        return f[i][cur][eor];
    }
    int digit = s[i] - '0';
    if(digit == cur) {
        // 不翻转
        Info t1 = dfs(i + 1, cur, eor^1);
        int flip = t1.flip, cnt = t1.cnt;
        // 翻转
        if(eor == 0) {
            Info t2 = dfs(i + 1, 1 - cur, 1);
            if(t2.flip + 1 < flip) {
                flip = t2.flip + 1;
                cnt = t2.cnt + (i > 1? 1: 0);
            }else if(t2.flip + 1 == flip) {
                cnt = min(cnt, t2.cnt + (i > 1? 1: 0));
            }
        }
        f[i][cur][eor].flip = flip;
        f[i][cur][eor].cnt = cnt;
        return f[i][cur][eor];
    }else {
        // 翻转
        Info t = dfs(i + 1, cur, eor^1);
        int flip = t.flip + 1, cnt = t.cnt;
        // 不翻转
        if(eor == 0) {
            Info t1 = dfs(i + 1, digit, 1);
            if(t1.flip < flip) {
                flip = t1.flip;
                cnt = t1.cnt + 1;
            }else if(t1.flip == flip) {
                cnt = min(cnt, t1.cnt + 1);
            }
        }
        f[i][cur][eor].flip = flip;
        f[i][cur][eor].cnt = cnt;
        return f[i][cur][eor];
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
       scanf("%d", &n);
       scanf("%s", s + 1);
       for(int i = 1; i <= n; i++) {
           for(int j = 0; j <= 1; j++) {
               for(int k = 0; k <= 1; k++) {
                   f[i][j][k].flip = f[i][j][k].cnt = -1;
               }
           }
       }
       Info res = dfs(1, s[1] - '0', 0);
       printf("%d %d\n", res.flip, res.cnt);
    }
    return 0;
}