解题思路

• 用一棵仅包含“目录”的树来模拟文件系统。每个结点表示一个目录，保存：

  • children：子目录名到子结点的映射
  • parent：父结点指针（便于 cd ..）

• 初始时创建根目录 /，并在其下创建默认目录 /usr，当前目录指向 /usr。

• 对每条指令：

  • mkdir name：若当前目录无同名子目录则创建。
  • cd ..：当前目录移动到其父目录。
  • cd name：移动到名为 name 的子目录（题目保证存在）。
  • ls：取出当前目录全部子目录名，按字典序升序排序并输出；若为空，输出单独一个空格。

• 算法要点：树+哈希映射（或字典）维护结构；ls 时对子目录名排序。

复杂度分析

• 设总指令数为 m，单个目录的子数为 k。
• 时间复杂度：除 ls 外均为 O(1) 平均；ls 为 O(k log k)（对子目录名排序）。
• 空间复杂度：O(N)，其中 N 为总目录数（由所有 mkdir 决定）。

代码实现

Python

# 中文注释版本
import sys

# 目录结点
class Node:
    def __init__(self, parent=None):
        self.parent = parent            # 父目录指针
        self.children = {}              # 子目录名 -> Node

# 文件系统功能：与主函数分离
class FileSystem:
    def __init__(self):
        self.root = Node(None)          # 根目录 /
        # 根下默认创建 /usr
        self.root.children["usr"] = Node(self.root)
        self.cur = self.root.children["usr"]  # 初始目录为 /usr

    def mkdir(self, name: str):
        # 若不存在同名子目录则创建
        if name not in self.cur.children:
            self.cur.children[name] = Node(self.cur)

    def cd(self, name: str):
        if name == "..":
            self.cur = self.cur.parent
        else:
            self.cur = self.cur.children[name]

    def ls(self) -> str:
        names = sorted(self.cur.children.keys())
        if not names:
            return " "                   # 无子目录则输出单独一个空格
        return " ".join(names)

def main():
    data = sys.stdin.read().strip().splitlines()
    if not data:
        return
    m = int(data[0].strip())
    fs = FileSystem()
    out = []
    idx = 1
    for _ in range(m):
        line = data[idx].strip()
        idx += 1
        if line == "ls":
            out.append(fs.ls())
        elif line.startswith("cd "):
            name = line[3:].strip()
            fs.cd(name)
        elif line.startswith("mkdir "):
            name = line[6:].strip()
            fs.mkdir(name)
        # 题目保证不会出现其他命令
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

Java

// 中文注释版本（ACM 风格，类名 Main）
import java.util.*;
public class Main {

    // 目录结点
    static class Node {
        Node parent;                               // 父目录
        HashMap<String, Node> children = new HashMap<>(); // 子目录映射
        Node(Node p) { this.parent = p; }
    }

    // 文件系统功能：与主函数分离
    static class FileSystem {
        Node root;
        Node cur;
        FileSystem() {
            root = new Node(null);                 // 根目录 /
            Node usr = new Node(root);
            root.children.put("usr", usr);         // 默认 /usr
            cur = usr;                              // 初始目录 /usr
        }
        void mkdir(String name) {
            if (!cur.children.containsKey(name)) {
                cur.children.put(name, new Node(cur));
            }
        }
        void cd(String name) {
            if ("..".equals(name)) cur = cur.parent;
            else cur = cur.children.get(name);     // 题目保证存在
        }
        String ls() {
            ArrayList<String> names = new ArrayList<>(cur.children.keySet());
            Collections.sort(names);
            if (names.isEmpty()) return " ";       // 无子目录输出一个空格
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < names.size(); i++) {
                if (i > 0) sb.append(' ');
                sb.append(names.get(i));
            }
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);  // m<=200，Scanner足够
        if (!sc.hasNextInt()) return;
        int m = sc.nextInt();
        sc.nextLine(); // 读掉行尾
        FileSystem fs = new FileSystem();
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < m; i++) {
            String line = sc.nextLine().trim();
            if (line.equals("ls")) {
                out.append(fs.ls()).append('\n');
            } else if (line.startsWith("cd ")) {
                String name = line.substring(3).trim();
                fs.cd(name);
            } else if (line.startsWith("mkdir ")) {
                String name = line.substring(6).trim();
                fs.mkdir(name);
            }
        }
        System.out.print(out.toString());
    }
}

C++

// 中文注释版本（ACM 风格）
#include <bits/stdc++.h>
using namespace std;

// 目录结点
struct Node {
    Node* parent;                                  // 父目录
    unordered_map<string, Node*> children;         // 子目录映射
    Node(Node* p = nullptr) : parent(p) {}
};

// 文件系统功能：与主函数分离
struct FileSystem {
    Node* root;
    Node* cur;
    FileSystem() {
        root = new Node(nullptr);                  // 根目录 /
        Node* usr = new Node(root);
        root->children["usr"] = usr;               // 默认 /usr
        cur = usr;                                  // 初始目录 /usr
    }
    void mkdir(const string& name) {
        if (!cur->children.count(name)) {
            cur->children[name] = new Node(cur);
        }
    }
    void cd(const string& name) {
        if (name == "..") cur = cur->parent;
        else cur = cur->children[name];            // 题目保证存在
    }
    string ls() {
        vector<string> names;
        names.reserve(cur->children.size());
        for (auto &kv : cur->children) names.push_back(kv.first);
        sort(names.begin(), names.end());
        if (names.empty()) return " ";             // 无子目录输出一个空格
        string res;
        for (size_t i = 0; i < names.size(); ++i) {
            if (i) res.push_back(' ');
            res += names[i];
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    if (!(cin >> m)) return 0;
    string dummy;
    getline(cin, dummy); // 读掉行尾
    FileSystem fs;
    string line;
    vector<string> output;

    for (int i = 0; i < m; ++i) {
        getline(cin, line);
        // 去除首尾空白
        auto l = line.find_first_not_of(" \t\r\n");
        auto r = line.find_last_not_of(" \t\r\n");
        if (l == string::npos) { --i; continue; }
        line = line.substr(l, r - l + 1);

        if (line == "ls") {
            output.push_back(fs.ls());
        } else if (line.rfind("cd ", 0) == 0) {          // 以 "cd " 开头
            string name = line.substr(3);
            // 去除可能空白
            size_t l2 = name.find_first_not_of(" \t");
            size_t r2 = name.find_last_not_of(" \t");
            name = (l2 == string::npos) ? "" : name.substr(l2, r2 - l2 + 1);
            fs.cd(name);
        } else if (line.rfind("mkdir ", 0) == 0) {       // 以 "mkdir " 开头
            string name = line.substr(6);
            size_t l2 = name.find_first_not_of(" \t");
            size_t r2 = name.find_last_not_of(" \t");
            name = (l2 == string::npos) ? "" : name.substr(l2, r2 - l2 + 1);
            fs.mkdir(name);
        }
    }

    for (size_t i = 0; i < output.size(); ++i) {
        cout << output[i] << "\n";
    }
    return 0;
}

题目内容

提供一个命令行软件，支持用户管理本地的文件系统。文件系统根目录为/，默认创建有/usr目录。命令行初始目录为/usr 。

命令行支持如下命令:

• mkdir:键入目录名，在当前目录下创建一个目录;当该目录下已经存在同名文件夹时，$mkdir$ 不会创建;

• cd ..: 回退到上一级目录;

• cd name进入当前目录下名为name的目录;

• ls:打印当前目录下所有子目录列表，字典序升序排列。

小华打开了该系统命令行程序，键入了m条指令，需要打印所有ls指令的执行结果。

注意:用例保证所有命令合法，即不会在/目录下cd ..，也不会cd一个不存在的目录。

输入描述

第一行输入一个整数 $m(m<=200)$，表示总共需要执行的命令条目数。

接下来 $m$ 行表示 $m$ 条命令，命令中所有路径不加双引号。

输入的命令不会包含题目描述之外的命令。目录名长度不超过 $20$ 个字符。

输出描述

输出所有ls指令的执行结果，每条ls结果打印一行，目录名用空格隔开。 若当前目录下没有子目录，则打印空格作为单独一行。

样例1

**输入

6
cd ..
ls
cd usr
mkdir usr1
mkdir usr2
ls

输出

usr
usr1 usr2