大意:给定一些序列,由下列组成,然后判断一个字符串属于什么样的类型。
simple stage O = A
fully-grown stage O = OAB
mutagenic stage O = BOA
Mutant O = other
思路:最开始时我没读懂题意,然后读了第二遍,然后是第三遍,最后发现,尼玛,这不就是编译原理里的上下文无关文法,还好我暑假看过一段时间的编译原理,要不是被这题目给绝对坑过了。
所谓的上下文无关文法就是给定几个算术表达式,然后通过一些相关的变化,可以推出另一个表达式。
回到题目,由图片可以知道, O = BOA,我们把BOA中的O看做一个表达式,这里O可以看做O = A | OAB | BOA,由此可知:
OAB推出的子串 OABAB, OABABAB,....AB的最后两位一定是AB。①
同理BOA推出的子串 BBOAA, BBBOAAA等,这样的子串特定是:首字母为B,尾字母为A。②
由1、2可以知道,他们的子串的长度一定是奇数,如果为偶数,那么字符串的类型一定是Mutant。
而O = A,则是 simple stage,同样为奇数。
至此,我们已经完整解答了本题,不过我还不清楚的是,这与动态规划有啥关系呢?
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <map> #include <queue> using namespace std; char answer[10][110] = {"SIMPLE", "FULLY-GROWN", "MUTAGENIC", "MUTANT"}; char str[10010]; void read_case() { scanf("%s", str); } void solve() { int f; read_case(); int len = strlen(str); if(len % 2 == 0) { f = 3; } else if(len == 1) { if(str[0] == 'A') f = 0; else f = 3; } else if(str[len-2] == 'A' && str[len-1] == 'B') { f = 1; } else if(str[0] == 'B' && str[len-1] == 'A') { f = 2; } else f = 3; printf("%s\n", answer[f]); } int main() { int T; scanf("%d", &T); while(T--) { solve(); } return 0; }