MX-J2-C 题解

思路

（没看讲评直播，但忽然想写一篇题解，如有不妥之处还请指出）

本题思路其实不难。简化题意就是：将字符串 $s$ 分割为若干子串，相邻两个子串不允许相同，求最多可分割为多少个子串。

是不是没说不可以是空串

注意到所有字符串长度之和最多为 $10^6$，直接暴力即可

如何暴力？本题可以用贪心的思想，不断枚举单个字符作为子串，如果当前子串与上一子串相同，那么再加一个字符进入当前子串即可。不过本题过于贪心是否会影响结果呢？为了让子串数量尽可能大，我们需要尽量让子串长度为 $1$；对于无法使子串长度为 $1$ 的情况，大家可以看看下面这个例子

我们正在处理如下字符串

Coffee_zzz

我们发现，当处理到第 $4$ 个字符时，发现新的子串与上一子串相同。这时我们其实有两种解决办法，分别是：

• 将第 $4$ 个字符 f 添加到第 $3$ 个字符所在的子串里

• 将第 $5$ 个字符串 e 添加到第 $4$ 个字符所在子串内

显然，如果我们选择后者，让第 $4$ 个字符 f 与第 $5$ 个字符 e 组成子串，则可以有效防止第 $5$ 个字符 e 所在子串（显然就是 e）与第 $6$ 个字符 e 相同这个问题。如果我们正在处理字符串 Coffee 的话，使用第一种方法将使该字符串不得不分为 {"C", "of", "f", "ee"}（$4$ 个子串），因为第 $6$ 个字符无法再往后寻找字符与它结合以避免与上一子串相同了，这使它不得不回过头与第 $5$ 个字符结合。反观方法二，其结果 {"C", "o", "f", "fe", "e"}（$5$ 个子串）显然比方法一的更优

于是我们得到一个性质：当存在两个相同字符，第二个字符将会与下一字符结合成为子串

如果有 $3$ 个或更多连续字符呢？枚举到第 $8$ 个字符 z 后，我们会认为它是第 $7$ 个子串，随后我们发现了第 $9$ 个字符 z 和第 $10$ 个字符 z，它们俩将不得不结合成为第 8 个子串 zz (于是这种方法生成了 $8$ 个子串). 不过，即使你把第 $7$ 个字符 _ 也拉进来，成为区间 _zzz，你会发现，即使把第一个 z 归为第 $6$ 个子串（成为 _z），也是无法使最后两个字符逃离组合在一起的命运，除非你把第二个 z 也归为第 $6$ 个子串，第三个 z 才会独自成为第 $7$ 个字符。最后我们得到了 $7$ 个子串，显然没有刚才的方法优秀

而如果有更多个呢？以字符串 akkkksc03 为例，第 $2$ 个字符 k 自己组成第 $2$ 个子串，接下来两个字符 k 结合在一起，最后一个 k 就能幸免遇难。对于多个连续字符，这些子串的长度以 $1$ 和 $2$ 交替出现（即子串 c 与 cc 交替出现，c 可以是任意字符）将会是最优决策。于是我们把原字符串分割为了 {"a", "k", "kk", "k", "s", "c", "0", "3"}，子串数量为 $8$，大家可以试试能不能分出更多的合法子串以推翻我的结论，我想你们是不会成功的。

如果我们的字符串的最后有好几个字符相同（比如 $4$ 个），代码的实现可能有点麻烦。然而，实际上，我们不需要作任何处理，枚举完字符串后直接输出答案并结束即可。为什么？看看这个例子：I_AK_IOI!!!!!

可以看到，该字符串的最后有 $5$ 个字符 !. 处理后会成为：{..., "!", "!!", "!", NULL}. 显然，我的方法会忽略最后一个字符 ! 并输出答案。区间 !!!!! 会少一个字符

不过，我们可以保证该区间第一个子串长度为 $1$ (这里是 !). 我们可以像牛顿摆一样把最后一个 ! 塞进最后一个子串内，并弹出该子串第一个字符，飞进上一个子串内，再弹出上上个子串的第一个字符……如果感觉难以理解的话，可以直接认为我把最后一个字符放到了该区间第一个子串的前一个子串里

于是该区间子串有：{..."I" + '!', "!", "!!", "!"}，也就是 {"I", "_", "A", "K", "_", "I", "O", "I!", "!", "!!", "!"}

于是我们成功地证明了我们的算法的正确性

解题方法

准备 $2$ 个临时字符串，一个用于存放当前尝试分割的子串 ((string)tot)，一个用于存放上一次成功分割的子串 ((string)lst)

使用单指针不断枚举字符串 $s$ 中的字符并加入当前尝试分割的子串 tot 中。如果当前子串与上一个子串 lst 不同，则认为该子串合法，更新字符串 lst，将答案 ans 加上 $1$，并将 tot 清空；否则不做处理。接着继续移动我们的指针，并把其指向的字符加入 tot 中，接着再次比较 tot 和 lst……直至所有字符被遍历完

最后，只需打印输出答案即可

将上面的过程循环执行 $T$ 次即可

复杂度

时间复杂度:

由于我们使用一个指针指向原字符串里各个字符，按顺序不断枚举，所以时间复杂度为 $\mathcal O(\sum_{i=1}^T n_i)$，也就是 $\mathcal O(\sum n)$. 题目给出 $\sum n\le 10^6$，可以通过本题。

空间复杂度:

我们使用了一个字符串存储待分割的字符串，这个字符串长度不定，但不会超过所有字符串长度 $10^6$（实际上，如果 $T=1$，字符串长度确实可以达到 $10^6$ 但不会超过），所以暂且认为其复杂度为 $\mathcal O(\sum n)$

常量 T 是一个整型，字符串 tot 和 lst 分别最多存储 $2$ 个字符，指针 p 无论是整型还是指针型都不会有多大。这些都可以忽略不计，我们可以认为空间复杂度就是 $\mathcal O(\sum n)$

Code

#include <iostream>
#include <string>

using namespace std;

string s, lst, tot;

int T, n, ans;

void work() {
    cin >> n >> s;
    // 重新赋值，防止上一轮循环影响
    ans = 0;
    lst = "";
    tot = "";
    // 此处第一次循环时，lst为空串，tot无论赋何值都不会受到影响，因此不需要在循环外先把lst赋一次值
    for (int i = 0; i < n; i++) {
        tot += s[i];
        if (tot != lst) lst = tot, tot = "", ans++;
    } cout << ans << endl;
}

int main() {
    cin >> T;
    for (int i = 0; i < T; i++)
        work();
    return 0;
}