P1624 单词缩写

    • 47通过
    • 297提交
  • 题目提供者 xmyzwls 管理员
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    树树发现好多计算机中的单词都是缩写,如GDB是全称Gnu DeBug的缩写。但是,有时候缩写对应的全称会不固定,如缩写LINUX可以理解为:

    (1) LINus’s UniX

    (2) LINUs’s miniX

    (3) Linux Is Not UniX

    现在树树给出一个单词缩写,以及一个固定的全称(若干个单词组成,空格隔开)。全

    称中可能会有无效的单词,需要忽略掉,一个合法缩写要求每个有效单词中至少有一个字符出现在缩写中,所写必须按顺序出现在全称中。

    对于给定的缩写和一个固定的全称,问有多少种解释方法?解释方法为所写的每个字母在全称每个有效单词中出现的位置,有一个字母位置不同,就认为是不同的解释方法。

    输入输出格式

    输入格式:

    第一行输入一个N,表示有N个无效单词;

    接下来N行分别描述一个由小写字母组成的无效单词;

    最后是若干个询问,先给出缩写(只有大写字母),然后给出一个全称,读入以“LAST CASE”结束。

    [数据规模]

    1≤N≤100,每行字符串长度不超过150,询问次数不超过20,最后方案数不超过10^9。

    输出格式:

    对于每个询问先输出缩写,如果当前缩写不合法,则输出“is not a valid abbreviation”,否则输出“can be formaed in i ways”(i表示解释方法数)

    输入输出样例

    输入样例#1: 复制
    2
    and
    of
    ACM academy of computer makers
    RADAR radio detection and ranging
    LAST CASE
    输出样例#1: 复制
    ACM can be formed in 2 ways
    RADAR is not a valid abbreviation
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。