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;}总结本题通过递归下降的方式根据生成规则逆向还原字符串的生长过程判断其是否属于健康集合。核心在于正确理解三种生长阶段的递归定义。利用字符串末尾和开头特征判断当前可能的阶段并递归检查剩余部分。注意优先级顺序但实际定义避免了重叠因此顺序影响不大。该解法直观易懂适用于这类形式语言判定的问题。若字符串长度较大可考虑使用迭代加下标索引优化但当前实现已足够通过测试。

相关新闻

最新新闻

DeepChem分子指纹终极指南:ECFP与FCFP如何选择?新手必看!

DeepChem分子指纹终极指南:ECFP与FCFP如何选择?新手必看!

DeepChem分子指纹终极指南:ECFP与FCFP如何选择?新手必看! 【免费下载链接】deepchem Democratizing Deep-Learning for Drug Discovery, Quantum Chemistry, Materials Science and Biology 项目地址: https://gitcode.com/GitHub_Trending…

2026/7/3 19:43:45
3个ExplorerPatcher部署故障的深度诊断与实战解决方案

3个ExplorerPatcher部署故障的深度诊断与实战解决方案

3个ExplorerPatcher部署故障的深度诊断与实战解决方案 【免费下载链接】ExplorerPatcher This project aims to enhance the working environment on Windows 项目地址: https://gitcode.com/GitHub_Trending/ex/ExplorerPatcher ExplorerPatcher作为Windows系统界面自定…

2026/7/3 19:43:45
SPI EEPROM与dsPIC30F硬件设计及数据存储管理

SPI EEPROM与dsPIC30F硬件设计及数据存储管理

1. 项目背景与硬件选型解析在嵌入式系统设计中,非易失性存储方案的选择直接影响产品的可靠性和用户体验。M95M04这颗4Mbit SPI EEPROM与dsPIC30F4011微控制器的组合,为存储用户偏好、日程设置等关键数据提供了理想的硬件平台。M95M04作为STMicroelectron…

2026/7/3 19:43:45
Gemini与Claude视觉创作能力实战对比:生成式AI工具选型指南

Gemini与Claude视觉创作能力实战对比:生成式AI工具选型指南

1. 项目概述:一场关于“视觉创作权”的真实较量2026年春天,我坐在工作室里,面前摊着三台设备:一台在跑Gemini 3.1 Pro生成的5秒海滩视频,一台正用Claude 3.5 Sonnet输出一份带交互节点的“量子计算原理”SVG流程图&…

2026/7/3 19:43:45
微信JS-SDK实现PC网页跳转小程序的Nuxt3实践

微信JS-SDK实现PC网页跳转小程序的Nuxt3实践

1. 项目背景与需求分析最近在开发一个企业官网项目时,客户提出了一个看似简单但实现起来颇有挑战的需求:需要在PC端网页中直接跳转到他们的小程序。这个需求在电商、教育、服务预约类网站中非常常见——当用户在电脑上浏览商品或服务时,能一键…

2026/7/3 19:43:45
NanoClaw:轻量级本地智能体框架,纯离线运行的文档处理助手

NanoClaw:轻量级本地智能体框架,纯离线运行的文档处理助手

1. 项目概述:为什么“本地优先”的轻量级智能体正在成为新刚需最近三个月,我陆续给六家中小团队做过技术咨询,几乎每场都会被问到同一个问题:“有没有一种智能体,不依赖云端API、不上传数据、不绑定厂商、装上就能跑&a…

2026/7/3 19:38:44

周新闻

月新闻