Moo Operations (USACO Bronze 2023 January)

Moo Operations (USACO Bronze 2023 January)

M和O组成的字符串，有四个操作：删除首字符、删除尾字符、用相反字符替换头（M、O互换）、用相反字符替换尾。 问最少多少次操作可以把字符串变成MOO，不可能则输出-1。

因为涉及不可能的情况，引导我们思考这四种操作有什么是不能做的，这时可以看到如果字符串最后变成了MOO， 那么中间位置的O一定是原来就存在的，四个操作都无法产生中间位置的这个O。进一步我们可以看到， 中间的这个O开始的时候一定不在字符串的首尾，因为四项操作都不能将首尾的字母放到最终字符串的中间。 所以我们得到一个中间结论，要想产生MOO，需要至少有一个在非首尾位置的O（必要条件）。

那这个条件是否是充分的呢？思考之后我们看到这的确是一个充分的条件，因为只要有一个非首尾的O，就可以“围绕”它把周围多余字母都删除， 然后把前面和后面字母换成M和O，就成功了。

然后我们要找最优解，有了上面的观察，应该可以看到从最初字符串的状态，能利用的状态尽量利用，就可以直接构造出最优解来。具体算法如下：

  1. 如果原字符串含有MOO，则可以利用，将周边字符删除即可。
  2. 或者在非尾的位置有MO，或者在非头的位置有OO，则删除多余字母，再将缺的一个字母替换即可。
  3. 如果在非头尾的位置有O，则删除多余字母后，替换得到M和O，就完成了。
  4. 否则-1.

上面这些操作可以直接调用C或者C++的字符串操作，实现起来最方便，当然手写也不复杂。以下程序使用C的字符串操作。 因为答案只需要操作次数，而不需要具体操作，所以并不需要生成操作过程，直接计算操作次数就可以了。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
 
int Q;
char s[105];    // len <= 100
 
int main() {
    scanf("%d", &Q);
    for (int q = 0; q < Q; q++) {
        scanf("%s", s);
        int len = strlen(s);
 
        if (strstr(s, "MOO")) {
            printf("%d\n", len-3);
        } else if (strstr(s, "MO") && strstr(s, "MO")-s < len-2 || strstr(s+1, "OO")) {    // MOX or XOO
            printf("%d\n", len-3+1);
        } else if (strstr(s+1, "O") && strstr(s+1, "O")-s < len-1) {                        // XOX
            printf("%d\n", len-3+2);
        } else
            printf("-1\n");
    }
    return 0;
}