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;
}

J2C. Turtle and Strings题解

题意

给定一个字符串 $s$, 要求将其拆分为若干个字符串 $t_1+t_2+...+t_k$ 的形式，要求相邻的两个字符串 $t_{i-1},t_i$ 互不相同，求能划分出来的字符串数量最大值。

解题方法

考虑贪心的去处理这个问题，也就是每次尝试划分当前能划分出来的最短字符串 $t_i$。

不难发现，当 $|t_{i-1}|>1$ 时，我们都可以划分出长度为 $1$ 的 $t_i$, 而当 $|t_{i-1}|=1$ 时，如果想划分出长度为 $1$ 的 $t_i$, 其充要条件是 $t_i\neq t_{i-1}$, 反之则一定会划分出长度为 $2$ 的 $t_i$。

接下来我们去证明为什么这样贪是对的。

如果说有比这样贪心做的更优解，那么一定是在某一个位置上没有取到暂时能取到的最小字符串。那么对于后面的待分解的字符串，就会减少一位可以提供贡献的值。而此时我们如果倒着去划分，所得到的最终贡献一定是小于等于之前的情况的（因为后面串的总长减小了，而相对关系却没变）。

例如对于 a|baabab，贪心的去做会划分出 a|b|aabab，而如果这个不是最优则说明 a|ba|abab 可以在 abab 中划分出比 aabab 更多的字符串。这显然是不可能的。

由此，贪心的正确性得证。

复杂度

时间复杂度:

$O(\sum{n})$

空间复杂度:

$O(\sum{n})$

Code

#include <bits/stdc++.h>
using namespace std;
int t,n;
string s;
signed main(){
	cin>>t;
    while(t--){
    	int nowlen=0,ans=0;
		//nowlen记录上一次划分的长度
    	cin>>n;
        cin>>s;
        for(int i=0;i<n;i++){
        	if(nowlen!=1){//上一次划分了长度非1的字符串
        		nowlen=1;//说明这一次一定可以划分长度为1的
        		ans++;
        	}else{//上一次划分的长度为1
        		if(s[i]!=s[i-1]){//如果当前字母与上一位不同，则说明可以继续划分长度为1的最优字符串
        			nowlen=1;
        			ans++;
        		}else{
        			nowlen=2;//否则只能让当前长度为2
        			if(i==n-1) ans--;//特判 因为如果是最后一位就构不成两个字母的字符串，只能和倒数第二位合体
        			i++;
        			ans++;
        		}
        	}
        }
        cout<<ans<<endl;
    }
	return 0;
}