题解 P1738 【洛谷的文件夹】

· · 题解

正如 kkk 所说，使用 C++ 的 STL，非常轻松。

首先来梳理一下思路。

  1. 题目问最少需要新建多少文件夹，即是问一共有多少个目录（因为每个文件夹只需要建立一次）。每次输入的数据可能会有重复的父文件夹，所以需要使用 \texttt{std::set} 来保存目录。
  2. 如何保存呢？因为每一级文件夹之间用 「/」隔开，所以只需要遍历一遍读入的字符串：
    1. 首先需要一个额外的字符串变量来保存已经遍历到的目录。
    2. 如果遇到「/」，就把当前字符串变量 \texttt{insert()} 到集合里面。
    3. 然后将字符串加上当前字符。
    4. 最后再 \texttt{insert()} 一次，以为最后一个字符不是「/」。
  3. 对于每一次询问，只需要输出当前集合大小再减一就好了。为什么要减去一？因为第一次 \texttt{insert()} 的时候是「/」，不算一个文件夹。

AC 代码就这几行。

//【P1738】洛谷的文件夹 - 洛谷 - 100
#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;
    }
}