【MX-J2-T2】Turtle and Strings

形式化题目

给定字符串 $s$ ，把它切分成若干连续非空段 $t_1, \ldots, t_k$ （拼接起来恰为 $s$ ），要求相邻两段不相等。求最大段数 $k$ 。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-14 15:01
 * update_at: 2026-08-14 15:35
 */
// brute.cpp：小数据暴力解，使用 01 序列 / 选择序列递归枚举所有可能。
// choose[i] = 1 表示在位置 i 与 i+1 之间切一刀，
// 枚举完整切分方案后，在叶子统一检查相邻段是否相同，并统计段数取最大。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n;
char s[MAXN];
int choose[MAXN]; // choose[i]：位置 i 与 i+1 之间是否切一刀（1 切，0 不切）
int best;

// 检查当前切分方案是否合法（相邻段不相同），返回段数；不合法返回 -1。
int check() {
    int cnt = 1;
    int start = 1; // 当前段的起点
    for (int i = 1; i < n; i++) {
        if (choose[i] == 1) {
            // 当前段 [start, i] 结束，找下一段 [i+1, nxt] 的终点 nxt
            int nxt = i + 1;
            while (nxt < n && choose[nxt] == 0) nxt++;

            int len1 = i - start + 1; // 当前段长度
            int len2 = nxt - i;       // 下一段长度
            if (len1 == len2) {
                bool same = true;
                for (int k = 0; k < len1; k++) {
                    if (s[start + k] != s[i + 1 + k]) {
                        same = false;
                        break;
                    }
                }
                if (same) return -1; // 相邻段相同，非法
            }
            cnt++;
            start = i + 1;
        }
    }
    return cnt;
}

void dfs(int dep) {
    if (dep == n) {
        int cnt = check();
        if (cnt > best) best = cnt;
        return;
    }
    for (int i = 0; i <= 1; i++) {
        choose[dep] = i;
        dfs(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        cin >> (s + 1);

        best = 0;
        dfs(1); // 枚举位置 1..n-1 的切分选择
        cout << best << '\n';
    }

    return 0;
}

brute.cpp 用 01 序列枚举所有切分：choose[i] = 1 表示在位置 $i$ 与 $i+1$ 之间切一刀，递归先生成完整的选择序列，到叶子再统一检查相邻段是否相同并统计段数。它枚举了 $2^{n-1}$ 种方案， $n = 10^6$ 时完全不可行。

三条观察把问题压缩成线性贪心：

存在最优解使每段长度不超过 2：段长不同则内容必不同；任意长度 $\geqslant 3$ 的段都能拆成更短的 1/2 段而不减少段数（对 $n \leqslant 8$ 的全部字符串枚举验证无例外）。
冲突只有一种：想取单字符段 $s[i]$ 时，唯一障碍是上一段恰好也是单个 $s[i]$ 。
双字符段永不冲突：取 $s[i]s[i+1]$ 后它长度是 2，与任何上一段比较都因长度不同而不同，之后下一段又是单字符，循环往复。

于是每步贪心：能取单字符段就取（段数 +1）；不能取就取双字符段（段数 +1）；只剩一个字符且仍冲突时并入上一段。

下面这张表展示样例 3（aaaaaa，答案 4）的贪心过程：

步骤	剩余部分	取的段	段数
1	aaaaaa	`a`（单字符）	1
2	aaaaa	`aa`（双字符，因再取 `a` 会与上段相同）	2
3	aaa	`a`（单字符）	3
4	aa	`aa`（双字符）	4

观察要点：单字符段与双字符段交替出现，这正对应"同字符相邻必冲突、双字符段靠长度不同避冲突"的规则；6 个字符切出 4 段，已无法更多（每 3 个字符最多 2 段）。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-14 15:01
 * update_at: 2026-08-14 15:45
 */
// P10841 【MX-J2-T2】Turtle and Strings
// 把 s 切成若干段，相邻段不能相同，求最大段数。
// 关键观察：存在最优解使每段长度 <= 2。
// 贪心：当前字符与上一段不同则取单字符段；
// 相同则必须取双字符段（双字符段长度 > 1，与上一段必然不同，永不冲突）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

int n;
char s[MAXN]; // 输入字符串

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        cin >> (s + 1);

        int ans = 0;
        char last_ch = '\0'; // 上一段的第一个字符
        int last_len = 0;    // 上一段的长度
        int i = 1;
        while (i <= n) {
            if (s[i] != last_ch || last_len > 1) {
                // 单字符段与上一段不同，直接取 s[i]
                last_ch = s[i];
                last_len = 1;
                ans++;
                i++;
            } else {
                // 单字符段与上一段相同，必须取双字符段 s[i]s[i+1]
                if (i + 1 <= n) {
                    last_ch = s[i];
                    last_len = 2;
                    ans++;
                    i += 2;
                } else {
                    break; // 只剩一个字符且与上一段相同，只能并入上一段
                }
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

复杂度

时间：每步消耗 1 或 2 个字符，每步 O(1)，总 $O(n)$ 。
空间： $O(n)$ 存字符串。

总结

这道题的关键是把"任意切分"收窄为"每段长度 ≤ 2"：相邻段相同要求内容完全相同，而长度是内容的一部分，所以段长不同就必然合法。于是冲突只剩"上一段是单字符且与当前字符相同"一种，取双字符段即可绕开——贪心每步都在合法前提下尽量多切。这类"切分 + 相邻不同"问题的通用手法是：先证明存在短段最优解，再逐位做局部决策。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18题意：切分 s 为若干连续段，相邻段不能相同，最大化段数
        |
        | 朴素：枚举 2^(n-1) 种切分（brute.cpp），指数爆炸
        v
关键观察
  段长不同 => 内容必不同
  存在最优解：每段长度 <= 2
  冲突唯一：上一段是单字符且 == s[i]
        |
        v
贪心扫描（main.cpp）
  能取单字符段？→ 取，段数+1，消耗 1 字符
  不能（冲突）？  → 取双字符段，段数+1，消耗 2 字符
  只剩 1 字符且冲突 → 并入上一段，结束
        |
        v
答案：段数累计
复杂度 O(n)，空间 O(n)

图中主线是"切分枚举 → 短段最优解 → 单/双字符贪心"。真正要抓住的是：长度是内容的一部分，所以"段短"天然规避了"段相同"。

子任务编号	分值	$n \le$	$\sum n \le$	特殊性质	子任务依赖
$1$	$18$	$9$	$10^4$	无	无
$2$	$21$	$50$	$10^3$	无	$1$
$3$	$12$	$10^6$	$10^6$	$s_1 = s_2 = \cdots = s_n$	无
$4$	$23$	$10^6$	$10^6$	恰好存在一个位置 $1 \le i \le n - 1$ 使得 $s_i \ne s_{i + 1}$	无
$5$	$26$	$10^6$	$10^6$	无	$1, 2, 3, 4$