[USACO2023-JAN-Bronze] T3 Moo Operations 题解

一、题目描述

因为Bessie觉得玩平时经常玩的只包含'C' 'O'和'W'的字符串无聊了，Farmer John 给了她Q个新的字符串(1≤Q≤100)，这Q个字符串只包含'M'和'O'。很明显，只包含M和O的单词里Bessie最喜欢的是”MOO”，所以她希望按照下面两个规则，将这Q个字符串转换成"MOO"：

1. 替换第一个或最后一个字符成为它相反的字符(O变成M，M变成O).

2. 删除第一个或最后一个字符.

很不幸的是，Bessie比较懒，不想做很多不必要的操作。对于每个字符串，请帮她找到最少操作次数使字符串变成”MOO”，如果不可能办到，输出-1 。

输入

第一行包含一个整数Q。

接下来Q行每行一个字符串，字符串中只包含M或O，字符串最少包含1个字符，最多包含100个字符。

输出

输出Q行，对于每个字符串，输出对应的操作次数。

样例

输入

复制

3

MOMMOM

MMO

MOO

输出

复制

4

-1

0

说明

A sequence of 4 operations transforming the first string into "MOO" is as follows:

• Replace the last character with O (operation 1)

• Delete the first character (operation 2)

• Delete the first character (operation 2)

• Delete the first character (operation 2)

The second string cannot be transformed into "MOO." The third string is already "MOO," so no operations need to be performed.

• Inputs 2-4: Every string has length at most 3.

• Inputs 5-11: No additional constraints.

二、分析

1. 只能从前或从后对字符串进行操作，那么结果必然是连续的字符串。

2. 最终的字符串结果是3，那么需要删除n-3个字符串

3. 中间是M，必然操作不到，所以中间必须是O

4. 枚举中间是O的长度为3的字符串

三、代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int main() {int t;scanf("%d",&t);while(t--){char s[202];scanf("%s",s);int len=strlen(s),ans=N;for(int i=1;i<len-1;i++){if(s[i]=='O'){int cur=len-3 + (s[i-1]=='M'?0:1)+(s[i+1]=='O'?0:1);ans=min(ans,cur);}}printf("%d\n",ans>=N?-1:ans);}return 0;
}