Moo Operations

题意

给定若干个只包含 M 和 O 的字符串。

一次操作可以：

把第一个或最后一个字符翻转成另一种字符；
删除第一个或最后一个字符。

问每个字符串最少多少次操作可以变成 "MOO"，不可能则输出 -1。

思路

先看一个真实模拟操作的 BFS 暴力：

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
79
80
81
82
83
84
85
86
87
88
89/**
 * 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-07-11 17:10
 * update_at: 2026-07-11 17:11
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

char opposite_char(char c) {
    if (c == 'M') {
        return 'O';
    }
    return 'M';
}

int bfs_solve(string start) {
    queue<string> q;
    map<string, int> dis;

    q.push(start);
    dis[start] = 0;

    while (!q.empty()) {
        string cur = q.front();
        q.pop();

        int d = dis[cur];
        if (cur == "MOO") {
            return d;
        }

        int len = (int)cur.size();
        if (len == 0) {
            continue;
        }

        string nxt;

        // 操作 1：翻转第一个字符。
        nxt = cur;
        nxt[0] = opposite_char(nxt[0]);
        if (dis.find(nxt) == dis.end()) {
            dis[nxt] = d + 1;
            q.push(nxt);
        }

        // 操作 1：翻转最后一个字符。
        nxt = cur;
        nxt[len - 1] = opposite_char(nxt[len - 1]);
        if (dis.find(nxt) == dis.end()) {
            dis[nxt] = d + 1;
            q.push(nxt);
        }

        // 操作 2：删除第一个字符。
        nxt = cur.substr(1);
        if (dis.find(nxt) == dis.end()) {
            dis[nxt] = d + 1;
            q.push(nxt);
        }

        // 操作 2：删除最后一个字符。
        nxt = cur.substr(0, len - 1);
        if (dis.find(nxt) == dis.end()) {
            dis[nxt] = d + 1;
            q.push(nxt);
        }
    }

    return -1;
}

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

    int q;
    cin >> q;
    while (q--) {
        string s;
        cin >> s;
        cout << bfs_solve(s) << '\n';
    }

    return 0;
}

这个暴力把每个字符串看成一个状态，用 BFS 尝试四种操作。它可以直接验证小数据的最短操作数，但状态数不适合满分数据。

满分做法从最终形态入手。

最终要得到长度为 3 的字符串。由于删除只能从两端进行，最后留下来的 3 个字符一定是原字符串中的一个连续长度 3 子串。

设这个子串是：

text

1s[i - 1], s[i], s[i + 1]

中间字符 s[i] 最后要成为 "MOO" 的第二个字符。可是当只剩 3 个字符时，中间字符不能被替换，所以它必须原本就是 O。

于是枚举所有内部位置 i，只考虑 s[i] == 'O' 的情况。

选择这个子串时：

删除左右多余字符需要 n - 3 次；
如果 s[i - 1] != 'M'，左端要替换一次；
如果 s[i + 1] != 'O'，右端要替换一次。

取所有候选的最小值即可。没有候选时输出 -1。

代码

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/**
 * 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-07-11 17:10
 * update_at: 2026-07-11 17:11
 */
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int solve(string s) {
    int n = (int)s.size();
    if (n < 3) {
        return -1;
    }

    int ans = INF;

    // 枚举最终保留下来的长度为 3 的子串的中间位置。
    for (int i = 1; i <= n - 2; i++) {
        if (s[i] != 'O') {
            continue;
        }

        int cur = n - 3; // 删除左右多余字符
        if (s[i - 1] != 'M') {
            cur++;
        }
        if (s[i + 1] != 'O') {
            cur++;
        }

        if (cur < ans) {
            ans = cur;
        }
    }

    if (ans == INF) {
        return -1;
    }
    return ans;
}

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

    int q;
    cin >> q;
    while (q--) {
        string s;
        cin >> s;
        cout << solve(s) << '\n';
    }

    return 0;
}

复杂度

每个字符串只扫描一遍。

单个询问时间复杂度为 $O(|S|)$ ，空间复杂度为 $O(1)$ 。

总结

本题不要从操作序列硬搜满数据，而要观察最终留下来的结构。

“只能删两端”说明最终三个字符来自连续子串；“只能改两端”说明中间字符必须已经是 O。有了这两个限制，枚举中间位置即可。

目录

题意

思路

代码

复杂度

总结