P2581 [ZJOI2005]Genotype

    • 7通过
    • 81提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 邻接矩阵 各省省选 2005 浙江 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    Genotype 是一个有限的基因序列。它是由大写的英文字母A-Z组成,不同的字母表示不同种类的基因。一个基因可以分化成为一对新的基因。这种分化被一个定义的规则集合所控制。每个分化的规则可以用三个大写字母A1A2A3表示,含义为基因A1可以分化成A2A3

    我们用S代表特种基因,繁殖genotype是从特种基因序列开始。根据给定的规则,它由被选择控制规则对基因不断进行繁殖而成。

    题目描述

    读入一个定义的规则集和一个想生成的genotypes 单词序列

    对每一个给定的 genotype,根据给定的分化规则,检查是否它能从某一个确定特种基因序列生成,如果能,找到最小的序列长度,

    输入输出格式

    输入格式:

    第一行有一个整数n, 1 <= n <= 10000. 下面n 每一行为一个分化规则. 这些规则都由包含A – Z的三个大写字母组成.

    接下来的10 行,每行有一个 genotype. Genotype由没有空格的单词组成,最多100 个英文大写字母.

    输出格式:

    有10行,在第I行应写入: 一个正整数――需要生成第I个genotypes的最小长度;或者单词 NIE, 如果不能生成对应的genotype。

    输入输出样例

    输入样例#1: 复制
    6
    SAB
    SBC
    SAA
    ACA
    BCC
    CBC
    ACBC
    
    输出样例#1: 复制
    1
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。