[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"：
替换第一个或最后一个字符成为它相反的字符(O变成M，M变成O).
删除第一个或最后一个字符.
很不幸的是，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.
二、分析
只能从前或从后对字符串进行操作，那么结果必然是连续的字符串。
最终的字符串结果是3，那么需要删除n-3个字符串
中间是M，必然操作不到，所以中间必须是O
枚举中间是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;
}