题目链接
题意
- 给我们一个有小写字母和‘ ?’ 组成的字符串,我们可以把 ?替换从任意小写字母,
- 如果不论我们怎么替换,这个字符串都会包含连续的 3 个元音字符或 5 个连续的辅音的话,这个串就是一个 bad 串。
- 如果不论我们怎么替换,这个字符串都不会包含连续的 3 个元音字符或 5 个连续的辅音的话,这个串就是一个 good 串。
- 否则是一个 mixed 串,
- 现在问我们 s 是那个类型的串?
思路
- 设 f1 [i][j] 表示在 i 个位置为结尾,有 j 个连续元音字符的这种情况是否存在,
- 设 f2 [i][j] 表示在 i 个位置为结尾,有 j 个连续辅音字符的这种情况是否存在,
- 之后按 s [i] 位置字符类型进行转移就行了,
- 如果 s [i] 是 ?
- 如果 s [i] 是元音
- 如果 s [i] 是辅音
代码
#include <bits/stdc++.h>
using namespace std;
#define db double
#define ll long long
#define sc scanf
#define pr printf
#define fi first
#define se second
#define pb push_back
#define m_p make_pair
#define Pir pair<int, int>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
/*==========ACMer===========*/
const int N = 55;
char s[N];
int f1[N][N], f2[N][N]; //f1[i][j] 表示前 i 个位置有 j 个元音的情况是否存在
//f2[i][j] 表示前 i 个位置有 j 个元音的情况是否存在
int trans(char ch)
{
if (ch == '?') return 2;
return (ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U');
}
int main()
{
int T, cas = 1; sc("%d", &T);
while (T --)
{
sc("%s", s + 1);
int n = strlen(s + 1);
for (int i = 1; i <= n; i ++) s[i] = trans(s[i]);
memset(f1, 0, sizeof f1);
memset(f2, 0, sizeof f2);
f1[0][0] = f2[0][0] = 1;
for (int i = 1; i <= n; i ++)
{
for (int j = 0; j <= 2; j ++)
{
if (f1[i - 1][j])
{
if (s[i] == 2 || s[i] == 0)
f2[i][1] = 1;
if (s[i] == 2 || s[i] == 1)
f1[i][j + 1] = 1;
}
}
for (int j = 0; j <= 4; j ++)
{
if (f2[i - 1][j])
{
if (s[i] == 2 || s[i] == 1)
f1[i][1] = 1;
if (s[i] == 2 || s[i] == 0)
f2[i][j + 1] = 1;
}
}
}
bool good = 0, bad = 0;
for (int i = 0; i <= 2; i ++) if (f1[n][i]) good = 1; //对于最后一个元素只要某个 f1[n][i] 为 1 (而这个 1 是从n-1位置的的某个位置j 状态f1[n - 1][]转移过来的....同理 f1[n-1][1] 为真也是从前 n-2 的某个合法状态转移来的),那么这个串一定存在在一个方案使这个串为good
for (int i = 0; i <= 4; i ++) if (f2[n][i]) good = 1; //与上同理
for (int i = 1; i <= n; i ++)
{
if (f1[i][3] || f2[i][5]) //只要有一个 bad 就存在一种方案为 bad
bad = 1;
}
pr("Case %d: ", cas ++);
if (good && bad)
pr("MIXED\n");
else if (good)
pr("GOOD\n");
else
pr("BAD\n");
}
return 0;
}