P1738 洛谷的文件夹

    • 103通过
    • 554提交
  • 题目提供者 kkksc03 站长团
  • 评测方式 云端评测
  • 标签 字符串 枚举,暴力 树形结构 模拟 洛谷原创
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    kkksc03是个非凡的空想家!在短时间内他设想了大量网页,然后总是交给可怜的lzn去实现。

    洛谷的网页端,有很多文件夹,文件夹还套着文件夹。

    例如:/luogu/application/controller表示根目录下有一个名称为luogu的文件夹,这个文件夹下有一个名称application的文件夹,其中还有名为controller的文件夹。

    每个路径的第1个字符总是’/’,且没有两个连续的’/’,最后的字符不是’/’。所有名称仅包含数字和小写字母。

    目前根目录是空的。kkksc03想好了很多应该有的文件夹路径名。问题是,需要是使这些文件夹都存在,需要新建几个文件夹呢?

    输入输出格式

    输入格式:

    输入文件第1行为一个正整数N。

    接下来N行,每行为一个描述路径的字符串,长度均不超过100。

    输出格式:

    输出应包含N行,每行1个正整数,第i行输出若要使第1个路径到第i个路径存在,最少需要新建多少个文件夹。

    输入输出样例

    输入样例#1: 复制
    2
    /luogu/application/controller
    /luogu/application/view
    
    输出样例#1: 复制
    3
    4
    
    输入样例#2: 复制
    3
    /chicken
    /chicken/egg
    /chicken
    输出样例#2: 复制
    1
    2
    2
    输入样例#3: 复制
    4
    /a
    /a/b
    /a/c
    /b/b
    输出样例#3: 复制
    1
    2
    3
    5

    说明

    数据规模:

    对于所有数据,N<=1000。

    对于20%数据,有N<=20;

    对于50%数据,有N<=200;

    对于30%数据,有对于所有路径最多存在两个’/’(包含第1个字符)。

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