#P1738. 洛谷的文件夹

    ID: 711 远端评测题 1000ms 128MiB 尝试: 2 已通过: 2 难度: 3 上传者: 标签>模拟字符串树形结构洛谷原创枚举暴力

洛谷的文件夹

题目描述

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

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

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

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

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

输入格式

输入文件第 11 行为一个正整数 NN

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

输出格式

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

2
/luogu/application/controller
/luogu/application/view

3
4

3
/chicken
/chicken/egg
/chicken
1
2
2
4
/a
/a/b
/a/c
/b/b
1
2
3
5

提示

数据范围及约定

  • 对于 20%20\% 数据,有 N20N \le 20
  • 对于 50%50\% 数据,有 N200N \le 200
  • 另有 30%30\% 数据,有对于所有路径最多存在两个 /\verb!/!(包含第 11 个字符);
  • 对于所有数据,N1000N \le 1000