专栏文章

题解：P3370 【模板】字符串哈希

HHuangRuibo
P3370题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipnfct0
此快照首次捕获于
2025/12/03 14:51
3 个月前
此快照最后确认于
2025/12/03 14:51
3 个月前
查看原文

题解

P3370 【模板】字符串哈希

题目传送门

题目重述

我们有 NN 个字符串，每个字符串都可能包含数字、大小写字母（注意大小写敏感哦！）。现在要统计这些字符串中有多少个是独一无二的。
比如输入：
TEXT
5
abc
aaaa
abc
abcc
12345
输出应该是4，因为有两个"abc"是重复的。

解题思路

暴力法？太慢啦！

最直接的想法是把所有字符串存下来，然后两两比较。但是当 N=10000N= 10000时，比较次数会达到恐怖的 50005000 万（ 107×510^7 \times 5 ）次！绝对会超时。

哈希表来拯救世界！

这时候就该我们的英雄 std::unordered_set 登场了！它就像一个有魔法的口袋：
  1. 每次往里面放字符串时，魔法会自动检查是否已经存在
  2. 如果已经存在，就悄悄忽略
  3. 最后数一数口袋里的东西就知道有多少独特的字符串啦！

std::unordered_set 是什么？

什么是哈希表？

想象你有一堆玩具要整理：
  • 普通箱子：要找一个玩具得从头翻到尾
  • 魔法箱子：每个玩具有个专属编号，直接就能找到它的位置
哈希表就是这样的魔法箱子！

unordered_set的魔法特性

  • 自动去重：相同的元素只保留一个
  • 无序但高效：不像 set 那样排序，所以速度更快

代码实现

CPP
#include<iostream>
#include<unordered_set>// 哈希表头文件
#include<string>
using namespace std;
int main()
{
    int N;
    cin>>N;
    unordered_set<string> str;// 定义哈希表
    for(int i=0;i<N;++i)
    {
        string s;
        cin>>s;
        str.insert(s);// 自动去重
    }
    cout<<str.size();// 独特元素数量就是答案
    return 0;
}

AC Record

为什么不用 set？

set虽然也能去重，但它......
  • 保持元素有序
而 unordered_set：
  • 元素无序
对于本题，我们不需要顺序，只要去重，所以 unordered_set 更合适！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...