自动搬运

查看原文

来自洛谷，原作者为

	Anguei 俺咕诶

搬运于2025-08-24 21:28:30，当前版本为作者最后更新于2018-03-14 22:53:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

首先来梳理一下思路。

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