P1738 洛谷的文件夹

题目描述

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

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

例如：$\text{/luogu/application/controller}$ 表示根目录下有一个名称为 $\text{luogu}$ 的文件夹，这个文件夹下有一个名称 $\text{application}$ 的文件夹，其中还有名为 $\text{controller}$ 的文件夹。

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

3
4

输入输出样例 #2

输入 #2

3
/chicken
/chicken/egg
/chicken

输出 #2

1
2
2

输入输出样例 #3

输入 #3

4
/a
/a/b
/a/c
/b/b

输出 #3

1
2
3
5

说明/提示

数据范围及约定

• 对于 $20\%$ 数据，有 $N\le 20$；
• 对于 $50\%$ 数据，有 $N\le 200$；
• 另有 $30\%$ 数据，有对于所有路径最多存在两个 $\text{/}$（包含第 $1$ 个字符）；
• 对于所有数据，$N\le 1000$。

C++实现

#include <set>
#include <string>
#include <iostream> 

int main() {
    int n;
    std::cin >> n;
    std::set<std::string> set;
    
    for (int i = 1; i <= n; ++i) {
        std::string s;
        std::cin >> s;
        std::string dir = "";
        for (auto j : s) {
            if (j == '/')
                set.insert(dir);
            dir += j;
        }
        set.insert(dir);
        
        std::cout << set.size() - 1 << std::endl;
    }
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容