P5266 【深基17.例6】学籍管理

题目描述

您要设计一个学籍管理系统，最开始学籍数据是空的，然后该系统能够支持下面的操作（不超过 \(10^5\) 条）：

插入与修改，格式 1 NAME SCORE：在系统中插入姓名为 \(\texttt{NAME}\)(由字母和数字组成不超过 \(20\) 个字符的字符串，区分大小写)，分数为 \(\texttt{SCORE}\)（\(0<\texttt{SCORE}<2^{31}\)）的学生。如果已经有同名的学生则更新这名学生的成绩为 \(\texttt{SCORE}\)。如果成功插入或者修改则输出 OK。
查询，格式 2 NAME：在系统中查询姓名为 \(\texttt{NAME}\) 的学生的成绩。如果没能找到这名学生则输出 Not found，否则输出该生成绩。
删除，格式 3 NAME：在系统中删除姓名为 \(\texttt{NAME}\) 的学生信息。如果没能找到这名学生则输出 Not found，否则输出 Deleted successfully。
汇总，格式 4：输出系统中学生数量。

输入格式

第一行，输入一个正整数 \(Q\)（\(1 \le Q \le 10^5\)），表示操作数量。

接下来 \(Q\) 行，每行先输入一个正整数 \(op\)（\(op \in [1,4]\)），表示操作种类。接着： - 如果 \(op = 1\)，则再输入一个字符串 \(\texttt{NAME}\) 以及一个正整数 \(\texttt{SCORE}\)，含义见题目描述。 - 如果 \(op = 2\)，则再输入一个字符串 \(\texttt{NAME}\)，含义见题目描述。 - 如果 \(op = 3\)，则再输入一个字符串 \(\texttt{NAME}\)，含义见题目描述。 - 如果 \(op = 4\)，则无需再输入其他内容。

输出格式

共输出 \(Q\) 行，每行输出一个字符串或正整数，为对应操作的处理结果，具体含义见题目描述。

输入输出样例 #1

输入 #1

5
1 lxl 10
2 lxl
3 lxl
2 lxl
4

输出 #1

OK
10
Deleted successfully
Not found
0

Tip

b站讲解链接

📌 题目分析

给定数据：

操作数量 Q ≤ 10^5
姓名字符串长度 ≤ 20
分数 SCORE < 2^31 (可以用 int 存下，但为求稳可使用 long long)

要求设计一个支持增改、查询、删除、统计总数四大操作的学籍系统。

👉 本质：

建立 字符串 (Key) 到 整数 (Value) 的一一映射关系

👉 类型：

数据结构 / 模拟 (C++ STL map 模板题)

🧠 解题思路

1️⃣ 为什么选用 C++ STL `map`？

对于需要通过“字符串”去查找“数字”的问题，如果手写字典树（Trie）或者哈希表，代码量会非常大且容易出错。 C++ 标准模板库（STL）中提供了极具威力的关联容器：std::map<string, int>。它天然支持键值对映射，并且内部自带计数和动态扩缩容，简直就是为了这道题量身定制的。

2️⃣ 操作与 map 方法的对应关系

操作 1（插入/修改）：mp[NAME] = SCORE。 map 的特性是，如果 NAME 不存在，它会自动创建；如果已经存在，直接覆盖原值，完美契合题意。
操作 2（查询）：使用 mp.count(NAME) 检查该学生是否存在。如果返回 1，说明存在，直接输出 mp[NAME]；返回 0 则输出 Not found。
操作 3（删除）：先用 mp.count(NAME) 检查。如果存在，使用 mp.erase(NAME) 将其彻底从系统中移除。
操作 4（汇总）：直接调用 mp.size()，它会以 \(O(1)\) 的时间复杂度返回当前容器中元素的个数。

3️⃣ 时间复杂度分析

std::map 底层是红黑树（一种自平衡二叉查找树）。

插入、查询、删除单次操作的复杂度均为 \(O(\log N)\)。
对于字符串键，还需要乘上字符串比较的长度 \(L\)。
总复杂度：\(O(Q \times L \log N)\)。对于 \(10^5\) 的操作量和最大 20 的字符串长度，总运算次数在千万级别，配合 I/O 优化，在 1 秒时限内毫无压力。

💻 C++代码

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
    // 算法竞赛必备的 I/O 优化，面对 10^5 级别的大数据输入极其关键
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;

    // 定义字典，键为姓名 (string)，值为成绩 (long long 保证不溢出)
    map<string, long long> mp;

    while (q--) {
        int op;
        cin >> op;

        if (op == 1) {
            string name;
            long long score;
            cin >> name >> score;
            mp[name] = score; // 存在则覆盖，不存在则新建
            cout << "OK\n";
        } 
        else if (op == 2) {
            string name;
            cin >> name;
            if (mp.count(name)) {
                cout << mp[name] << "\n";
            } else {
                cout << "Not found\n";
            }
        } 
        else if (op == 3) {
            string name;
            cin >> name;
            if (mp.count(name)) {
                mp.erase(name); // 从系统中删除
                cout << "Deleted successfully\n";
            } else {
                cout << "Not found\n";
            }
        } 
        else if (op == 4) {
            cout << mp.size() << "\n"; // 输出当前学生总数
        }
    }

    return 0;
}

⚠️ 易错点

❌ 1. 滥用 `[]` 运算符进行查询

很多人在操作 2 查询时，会直接写 if (mp[name] > 0) 甚至直接输出。 大忌！ map 的 [] 运算符有一个极其危险的副作用：如果你查询的 Key 不存在，它会自动帮你创建一个默认值为 0 的元素！这不仅会导致你输出错误的结果，更致命的是它会增加 map.size() 的大小，直接让操作 4（汇总总数）全盘崩溃。 正确做法：查询和删除前，必须先使用 mp.count(name) 或 mp.find(name) 来判断存不存在。

❌ 2. 忘记加速输入输出流

操作量高达 \(10^5\) 次，而且伴随着大量的字符串读取和换行输出。如果习惯性地使用 endl，会导致缓冲区频繁刷新，极大概率会触发 TLE（超时）。使用 \n 并加上 ios::sync_with_stdio(false); 是基本素养。

🚀 一句话总结

将姓名作为键，分数作为值，利用 STL map 丝滑实现增删改查。牢记“查询不越界，判断用 count”。

🔥 补充：硬核知识点

std::map 与 std::unordered_map 的抉择

这道题除了使用 <map>，其实还可以使用 <unordered_map>。在算法竞赛中，什么时候用哪个是一门学问：

std::map (红黑树)
- 特点：内部元素会自动按照 Key 的字典序升序排列。
- 复杂度：稳定 \(O(\log N)\)。
- 适用场景：需要按顺序输出/遍历、或者题目求最值（有 upper_bound 等操作）。最关键的是它绝对稳定，不会被恶意测试数据卡。
std::unordered_map (哈希表)
- 特点：内部元素是无序的。
- 复杂度：理论平均 \(O(1)\)，极其狂暴。
- 致命弱点：如果题目出题人恶意构造了大量 Hash 冲突的字符串（即著名的 Hash Killer 数据），它的最坏复杂度会退化到 \(O(N)\)，导致程序直接超时被 TLE 抬走。

竞赛法则： 如果题目不需要排序，且对时间要求极度苛刻，上 unordered_map；但如果时间给得够（比如这题 1s 跑 \(10^5\) 次 \(O(\log N)\) 完全够用），老老实实用 map，保命最重要！