第三题 - NEWFOLDER(1) 题目跳转：新建文件夹(1)。 也是一道水题，用 STL 的 unordered_map/ map 存一下某一个字符串出现的次数就可以了。由于 NNN 比较大，因此如果直接用双层循环遍历的话绝对会超时。 但需要注意的是，map 的单次插入/查询的时间复杂度约为 O(log⁡2N)O(\log_2 N)O(log2 N)。因此本题的综合时间复杂度约为 O(Nlog⁡2N)O(N \log_2 N)O(Nlog2 N)。 本题的 AC 代码如下：

你们自己看吧（祝你们看懂，我懒得写注释了） 顺便说一句，我的内存暂时是最低的，真不错！！！

题目解析 令 L=10L=10L=10 为字符串的最大长度。 如果我们每次都按照题目描述中的的那样去暴力查找统计与 SiS_iSi 相同的字符串的数量，则总共需要花费 Ω(N2)\Omega(N^2)Ω(N2) 时间，从而导致 TLE\tt{TLE}TLE（超时）。 我们可以使用 std::map 来存储“到目前为止 SiS_iSi 出现的次数”（Python\tt{Python}Python 可以使用 defaultdict(int)），这样对于每个字符串 SiS_iSi 可以在 O(Llog⁡N)\mathrm{O}(L\log N)O(LlogN) 的时间内确定要输出的字符串。 通过这种方法，可以在总共 O(NLlog⁡N)\mathrm{O}(NL\log N)O(NLlogN) 的时间内解决问题。 语法小课堂 1. std::map<K, V> 可以创建一个具有 (K:V)(K: V)(K:V) 映射关系的容器，对于本题中，我们希望给出一个字符串，就能够获取其出现的次数，实际上是要建立一个关于 (string:int)(\tt{string: int})(string:int) 的映射关系。那么访问时就可以像数组那样使用 [] 访问。 2. 对于 Python\tt{Python}Python 推荐使用 defaultdict 而非内置的 dict。 defaultdict 会在尝试访问字典中不存在的 键 时，给定一个 默认值，例如使用 defaultdict(int) 创建字典时，若访问到当前字典中不存在的 键 时，就会返回 0，而非直接报错，其行为更接近 C++ 的 std::map。 AC代码 C++ 代码： Python 代码：