1 条题解
-
0
成绩映射表 · 讲解
思路与接口
使用
map<string,long long>,key 是姓名,value 是分数。- 写入使用
scores[name]=score,同一 key 自动覆盖,不会增加不同姓名数量。 - 查询使用
find(name);返回end()表示不存在,输出NOT_FOUND,否则读it->second。 erase(name)返回被删掉的 key 数量。map 的 key 不重复,所以这个值恰为 0 或 1。size()就是当前不同姓名的数量。
正确性
map 保证同一姓名最多一条记录。SET 精确写入或覆盖对应键,ERASE 精确删除对应键,FIND 不修改容器并返回该键的当前值,COUNT 返回键数。因此 map 始终与题目描述的成绩表相同。
复杂度
姓名长度最多 20,可视为固定上界。单次写入、查询、删除 O(log q),COUNT 为 O(1),总时间 O(q log q),空间 O(q)。也可以用
unordered_map重做并讨论平均复杂度与哈希行为。常见错误
- 用
scores[name]做查询:不存在时会插入分数 0,既无法输出NOT_FOUND,又改变后续计数和删除结果。配套错误程序展示此错误。 - 通过“分数是否为 0”判断是否存在;合法记录可以保存 0。
- 覆盖时把数量加一,或删除失败仍减少数量。
- 混淆
a、ab等不同姓名。
数据验证说明
独立 Python 字典明确使用 key 是否存在来判断查询和删除。正式数据覆盖空表、反复覆盖、重复删除、最长姓名和大量不存在的查询;额外 token、非法姓名或分数会被拒绝。
原创来源记录
本题题面、样例、代码、讲解与数据从零编写。只使用公开的算法概念和 C++ 标准库接口,没有使用第三方题面、故事、程序或测试文件。
C++17 参考实现
#include <iostream> #include <map> #include <string> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; map<string, long long> scores; while (q--) { string op; cin >> op; if (op == "COUNT") { cout << scores.size() << '\n'; } else { string name; cin >> name; if (op == "SET") { long long score; cin >> score; scores[name] = score; } else if (op == "FIND") { auto it = scores.find(name); if (it == scores.end()) cout << "NOT_FOUND\n"; else cout << it->second << '\n'; } else { cout << scores.erase(name) << '\n'; } } } } - 写入使用
- 1
信息
- ID
- 5263
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者