原题目链接：P2580 于是他错误的点名开始了 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
原题目截图：
思路分析：
解法一：哈希表法
显而易见的一种思路，我们不妨模拟一下：
当教练每次点名，我作为特派员，便查看一下有没有这个学生，是不是点过了这个学生。
我们查看的过程，就依赖于一张表，这张表应该记录如下信息：
【学生姓名：点名次数】
但是我们知道，查表得一个一个看，看名字是不是对得上，这样当数据量很大的时候，一定会超时。
因此，我们就得用上新的数据结构了：哈希表。
C++中的哈希表是一种基于哈希函数的数据结构，它通过哈希函数将键（key）映射到表中一个位置来访问记录，从而实现快速的数据访问。哈希表可以用于快速查找、插入和删除操作。
在C++里面，我们可以直接调用头文件include<unordered_map>来使用基于红黑树的哈希。
我们使用哈希表存储，当判断学生名字是否存在时，这一步骤平均时间复杂度几乎是常数。
解法二：字典树法
我们简要说一下字典树的作用：
字典树（Trie），又称前缀树或查找树，是一种用于快速检索字符串数据集中的键的数据结构。它特别适合于实现自动补全、拼写检查、IP 路由等功能。字典树的每个节点代表一个字符，从根节点到某一节点的路径表示一个字符串。
字典树的适用场景：
-
字符串检索：在一组字符串集合中快速检索某个字符串是否存在。（因此这道题用字典树也可以做）
-
前缀匹配：实现自动补全功能，例如搜索引擎的搜索建议。
-
拼写检查：检测用户输入的单词是否拼写正确，并提供可能的正确拼写。
-
IP 地址路由：在 IP 路由中，快速查找特定 IP 地址对应的路由。
-
词频统计：统计字符串集合中每个单词出现的次数。
-
字符串排序：利用字典树可以快速对字符串进行排序。
-
数据压缩：例如，用于字符串的压缩存储，通过共享公共前缀来减少存储空间。
-
最长公共前缀（LCP）问题：快速找到一组字符串的最长公共前缀。
-
模式匹配：用于文本搜索中的模式匹配问题，如 KMP 算法中的部分匹配表（也称为失败函数）。
字典树的特点：
-
空间效率：对于有大量公共前缀的字符串集合，字典树可以节省存储空间。
-
时间效率：在理想情况下，插入和查找操作的时间复杂度为 O(m)，其中 m 是字符串的长度。
解决代码：
解法一：哈希表法
#include<iostream>
using namespace std;
#include<unordered_map>
int main() {
int n;
cin >> n;
unordered_map<string, int>ump;
for (int i = 0; i < n; i++) {
string name;
cin >> name;
ump[name]++;
}
int m;
cin >> m;
for (int i = 0; i < m; i++) {
string name;
cin >> name;
if (!ump.count(name)) cout << "WRONG" << endl;
if (ump[name] > 1) {
cout << "REPEAT" << endl;
continue;
}
if (ump[name] == 1) {
cout << "OK" << endl;
ump[name]++;
}
}
return 0;
}解法二：字典树法
#include<iostream>
using namespace std;
#include<unordered_map>
struct trienode {
char val;
unordered_map<char,trienode*>ump;
bool isend;
int num;//点名次数
trienode(char val) :val(val),isend(false),num(0){
}
void insert(string word) {
trienode* cur = this;
for (char ch : word) {
if (!cur->ump.count(ch)) {
cur->ump[ch] = new trienode(ch);
}
cur = cur->ump[ch];
}
cur->isend = true;
return;
}
int search(string word) { //没找到就返回-1，找到了就返回单词的点名次数
trienode* cur = this;
for (char ch : word) {
if (!cur->ump.count(ch)) return -1;
cur = cur->ump[ch];
}
if (cur && cur->isend) {
int ret = cur->num;
cur->num++;
return ret;
}
}
};
int main() {
trienode tree('*'); //根节点
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string name;
cin >> name;
tree.insert(name);
}
int m;
cin >> m;
for (int i = 0; i < m; i++) {
string name;
cin >> name;
int judge = tree.search(name);
if (judge == -1) cout << "WRONG" << endl;
else if (judge == 0) cout << "OK" << endl;
else cout << "REPEAT" << endl;
}
return 0;
}今天的博客就写的到这里了，愿诸君共勉之！
标签：洛谷,name,int,哈希,P2580,字符串,字典,cur From： https://blog.csdn.net/weixin_70448721/article/details/142636794