UVa 620 Cellular Structure

题目描述某种微生物的细胞链由A和B两种细胞组成。若未发生变异其生长链符合以下递归定义简单阶段simple stageO A完全生长阶段fully-grown stageO OAB致突变阶段mutagenic stageO BOA即一个健康的细胞链要么是单独的A要么是一个健康链后接AB要么是B后接一个健康链再接A。若一个链同时符合多种阶段则按SIMPLE、FULLY-GROWN、MUTAGENIC的优先级输出。若不符合以上任一正常形态则输出MUTANT。输入格式第一行为一个整数nnn表示待测试的细胞链数量。接下来nnn行每行为一个由A和B组成的字符串。输出格式对于每个细胞链输出一行结果SIMPLEFULLY-GROWNMUTAGENICMUTANT样例输入4 A AAB BAAB BAABA输出SIMPLE FULLY-GROWN MUTANT MUTAGENIC题目分析本题给出了一种递归定义的字符串集合——健康细胞链。基本单元是A并允许通过两种变换扩展在末尾添加AB成为完全生长或在两端分别添加B和A成为致突变。判断一个给定字符串是否属于这个集合并给出具体类别。由于变换规则是对称的我们可以从外向内递归检查。对于长度为111的字符串仅当为A时是简单阶段。对于长度大于111的字符串考虑其最后两个字符若结尾为B且前面一个字符为A则可能属于完全生长阶段删除末尾的AB后剩余部分必须是一个健康链。若结尾为A且开头为B则可能属于致突变阶段删除首尾的B和A后剩余部分必须是一个健康链。递归地剩余部分继续判断直到长度为111或无法匹配。注意优先级SIMPLE仅当字符串恰好为A时成立FULLY-GROWN和MUTAGENIC不会重叠因为它们的末尾字符不同B与A所以按顺序判断即可。解题思路递归函数设计定义三个函数is_simple(s)当s A时返回true否则false。is_fully_grown(s)若s长度小于等于222返回false。若s最后一个字符为B删除最后一个字符后若新的最后一个字符为A则删除末尾两个字符对剩余部分递归调用is_simple、is_fully_grown、is_mutangenic的并集即只要剩余部分是健康链即可。否则返回false。is_mutangenic(s)若s长度小于等于222返回false。若s最后一个字符为A删除最后一个字符后若第一个字符为B则删除首尾字符对剩余部分递归调用上述三个函数。否则返回false。由于递归定义中一个健康链可以是简单、完全生长或致突变因此is_fully_grown和is_mutangenic在检查内部时需允许三种可能。代码中直接调用三个函数进行逻辑或等价于判断剩余部分是否为健康链。主流程对每个字符串按优先级依次调用is_simple、is_fully_grown、is_mutangenic若任一返回true则输出对应结果否则输出MUTANT。复杂度分析每个递归步骤删除两个字符递归深度为O(L)O(L)O(L)其中LLL为字符串长度。但每次递归都会创建字符串副本通过erase和拷贝总时间复杂度为O(L2)O(L^2)O(L2)。由于本题未给出长度上限但实际数据通常不大该实现可通过。若需优化可使用下标索引代替拷贝但当前方案简洁有效。代码实现// Cellular Structure// UVa ID: 620// Verdict: Accepted// Submission Date: 2016-08-28// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;boolis_fully_grown(string cell);boolis_mutangenic(string cell);boolis_simple(string cell){returncell.length()1cell.front()A;}boolis_fully_grown(string cell){if(cell.length()2)returnfalse;if(cell.back()B){cell.erase(cell.end()-1);if(cell.back()A){cell.erase(cell.end()-1);returnis_simple(cell)||is_fully_grown(cell)||is_mutangenic(cell);}}returnfalse;}boolis_mutangenic(string cell){if(cell.length()2)returnfalse;if(cell.back()A){cell.erase(cell.end()-1);if(cell.front()B){cell.erase(cell.begin());returnis_simple(cell)||is_fully_grown(cell)||is_mutangenic(cell);}}returnfalse;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn;cinn;string line;for(inti1;in;i){cinline;if(is_simple(line))coutSIMPLE\n;elseif(is_fully_grown(line))coutFULLY-GROWN\n;elseif(is_mutangenic(line))coutMUTAGENIC\n;elsecoutMUTANT\n;}return0;}总结本题通过递归下降的方式根据生成规则逆向还原字符串的生长过程判断其是否属于健康集合。核心在于正确理解三种生长阶段的递归定义。利用字符串末尾和开头特征判断当前可能的阶段并递归检查剩余部分。注意优先级顺序但实际定义避免了重叠因此顺序影响不大。该解法直观易懂适用于这类形式语言判定的问题。若字符串长度较大可考虑使用迭代加下标索引优化但当前实现已足够通过测试。