P2030 遥控车

    • 38通过
    • 153提交
  • 题目提供者 LittleZ
  • 评测方式 云端评测
  • 标签 二分答案 字符串 递推 高精 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    平平带着韵韵来到了游乐园,看到了n辆漂亮的遥控车,每辆车上都有一个唯一的名字name[i]。韵韵早就迫不及待地想玩名字是s的遥控车。可是韵韵毕竟还小,她想象的名字可能是一辆车名字的前缀(也就是说能确定一个i,使s是name[i]的前缀),这时她就能玩第i辆车;或者是一个无中生有的名字,即s不是任何一辆车名字的前缀,这时候她什么也不能玩。

    你需要完成下面的任务:

    1.韵韵想了m个她想要的名字,请告诉她能玩多少次。

    2.由于管理员粗心的操作,导致每辆车的摆放位置都可能出现微小的差错,原来第i辆车现在的位置可能是i-1、i、i+1中的任意一个(第1辆车的位置不可能是0,第n辆车的位置不可能是n+1)。请你计算出共有多少种可能的排列。

    注:数据保证当s是name[i]的前缀时,i是唯一确定的。一辆车可以玩多次。

    输入输出格式

    输入格式:

    第一行是2个正整数n、m。

    接下来n行,每行1个字符串name[i],表示第i辆车的名字。接下来m行,每行1个字符串s,表示韵韵想要的名字。

    输出格式:

    第一行输出韵韵能玩的次数。第二行输出共有多少种可能的排列。

    输入输出样例

    输入样例#1: 复制
    4 4
    Abcd
    DeF
    AAa
    aBccc
    Ab
    AA
    AbC
    aBcc
    输出样例#1: 复制
    3
    5
    

    说明

    【注意】

    对于题目涉及到的字符串严格区分大小写,且长度小于255。

    【数据范围】

    对于20%的数据 n≤10,m≤10;

    对于40%的数据 n≤1000,m≤1000;

    对于100%的数据 n≤10000,m≤10000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。