UVa 620 Cellular Structure

题目描述

某种微生物的细胞链由A和B两种细胞组成。若未发生变异，其生长链符合以下递归定义：

• 简单阶段（simple stage）：O = A
• 完全生长阶段（fully-grown stage）：O = OAB
• 致突变阶段（mutagenic stage）：O = BOA

即一个健康的细胞链要么是单独的A，要么是一个健康链后接AB，要么是B后接一个健康链再接A。若一个链同时符合多种阶段，则按SIMPLE、FULLY-GROWN、MUTAGENIC的优先级输出。若不符合以上任一正常形态，则输出MUTANT。

输入格式

第一行为一个整数nnn，表示待测试的细胞链数量。接下来nnn行，每行为一个由A和B组成的字符串。

输出格式

对于每个细胞链，输出一行结果：

• SIMPLE
• FULLY-GROWN
• MUTAGENIC
• MUTANT

样例

输入

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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;boolis_fully_grown(string cell);boolis_mutangenic(string cell);boolis_simple(string cell){returncell.length()==1&&cell.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;cin>>n;string line;for(inti=1;i<=n;i++){cin>>line;if(is_simple(line))cout<<"SIMPLE\n";elseif(is_fully_grown(line))cout<<"FULLY-GROWN\n";elseif(is_mutangenic(line))cout<<"MUTAGENIC\n";elsecout<<"MUTANT\n";}return0;}

总结

本题通过递归下降的方式，根据生成规则逆向还原字符串的生长过程，判断其是否属于健康集合。核心在于：

• 正确理解三种生长阶段的递归定义。
• 利用字符串末尾和开头特征判断当前可能的阶段，并递归检查剩余部分。
• 注意优先级顺序，但实际定义避免了重叠，因此顺序影响不大。

该解法直观易懂，适用于这类形式语言判定的问题。若字符串长度较大，可考虑使用迭代加下标索引优化，但当前实现已足够通过测试。