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

题意

维护学生姓名和成绩，支持插入或修改、查询、删除，以及输出当前学生人数。

思路

姓名唯一确定一名学生，成绩是随姓名保存的值，正好对应字典的 key -> value 模型：

students[name]=score：插入新学生或覆盖旧成绩；
name in students：判断学生是否存在；
students[name]：取得成绩；
del students[name]：删除；
len(students)：当前人数。

逐条模拟即可，不需要自己实现哈希表。

Python 知识

字典赋值天然同时覆盖“插入”和“修改”两种情况。
查询前先用 in 判断，避免不存在的键触发 KeyError。
del mapping[key] 删除指定键值对，len(mapping) 直接得到记录数。
姓名保留为 bytes 也可以作为字典键，减少批量输入后的解码工作。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：字典的增删改查模式。
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：按不同操作参数个数解析 token。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38import sys


def main():
    data = sys.stdin.buffer.read().split()
    q = int(data[0])
    pos = 1
    students = {}
    answer = []

    for _ in range(q):
        operation = int(data[pos])
        pos += 1
        if operation == 1:
            name, score = data[pos], int(data[pos + 1])
            pos += 2
            students[name] = score
            answer.append("OK")
        elif operation == 2:
            name = data[pos]
            pos += 1
            answer.append(str(students[name]) if name in students else "Not found")
        elif operation == 3:
            name = data[pos]
            pos += 1
            if name in students:
                del students[name]
                answer.append("Deleted successfully")
            else:
                answer.append("Not found")
        else:
            answer.append(str(len(students)))

    print("\n".join(answer))


if __name__ == "__main__":
    main()

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87/**
 * P5266 【深基17.例6】学籍管理
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXQ = 100005;
const int MOD = 100003;

// 哈希表（链地址法）：名字→成绩
// 名字用 base-27 编码成 unsigned long long
struct Entry {
    unsigned long long key;
    int score;
    int next;
} tbl[MAXQ];
int head[MOD], cnt;

unsigned long long encode(const char *s) {
    unsigned long long h = 0;
    for (int i = 0; s[i]; ++i)
        h = h * 27 + (s[i] - 'a' + 1);
    return h;
}

void set_score(unsigned long long key, int score) {
    int idx = key % MOD;
    for (int i = head[idx]; i; i = tbl[i].next) {
        if (tbl[i].key == key) { tbl[i].score = score; return; }
    }
    ++cnt;
    tbl[cnt].key = key;
    tbl[cnt].score = score;
    tbl[cnt].next = head[idx];
    head[idx] = cnt;
}

int get_score(unsigned long long key) {
    int idx = key % MOD;
    for (int i = head[idx]; i; i = tbl[i].next)
        if (tbl[i].key == key) return tbl[i].score;
    return -1;
}

void erase_key(unsigned long long key) {
    int idx = key % MOD;
    for (int i = head[idx]; i; i = tbl[i].next) {
        if (tbl[i].key == key) { tbl[i].score = -1; return; }
    }
}

int main() {
    int q;
    scanf("%d", &q);
    while (q--) {
        int op;
        scanf("%d", &op);
        if (op == 1) {
            char name[15];
            int score;
            scanf("%s%d", name, &score);
            set_score(encode(name), score);
            puts("OK");
        } else if (op == 2) {
            char name[15];
            scanf("%s", name);
            int s = get_score(encode(name));
            if (s == -1) puts("Not found");
            else printf("%d\n", s);
        } else if (op == 3) {
            char name[15];
            scanf("%s", name);
            unsigned long long key = encode(name);
            if (get_score(key) == -1) puts("Not found");
            else { erase_key(key); puts("Deleted successfully"); }
        } else {
            printf("%d\n", cnt);
        }
    }
    return 0;
}

复杂度

每次操作期望时间复杂度 $O(1)$ ；字典最多保存 $O(q)$ 名学生，空间复杂度 $O(q)$ 。

总结

先识别数据模型：唯一姓名是键，成绩是值。Python 字典已经完整提供这类管理系统需要的操作。

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

目录

题意

思路

Python 知识

代码

复杂度

总结