1 条题解

  • 0
    @ 2026-11-16 20:48:26

    成绩映射表 · 讲解

    思路与接口

    使用 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
    上传者