题目来源：改编自牛客网 KY53 查找学生信息（王道机试指南原题）。本 Lab 使用课程自定义输入输出协议和独立测试，不复制来源站点的代码或测试。

学习目标

• 以学号字符串为键手写散列索引（散列函数 + 链地址冲突处理），支持期望 $O(|id|)$ 的查询；
• 对比“学号做数组下标”的直接定址与“散列映射”两种口径，算清 6 位学号的空间账；
• 按 %.1f 口径格式化输出浮点数，处理命中与 No Answer! 两种输出分支。

前置知识与环境

先阅读第 9.2 节 散列表的“从关键字到地址”与“链地址法”两节，重点体会“散列函数设计”：学号是字符串键，先要把它映射成整数，再压缩进表长范围。

在 Lab 目录执行 make doctor 检查环境；未安装 Make 时可在仓库根使用 pnpm 兜底命令（见下文“运行”）。

任务

先读入 n 条学生记录，每条为 学号 姓名 语文 数学 英语；随后进行 m 次查询，每次给定一个学号。对每次查询输出一行：

• 若学号存在：输出 学号 姓名 成绩1 成绩2 成绩3，三个成绩各保留 1 位小数（如 78 输出 78.0）；
• 若学号不存在：输出 No Answer!。

注意：学号是字符串键，允许前导零（如 012345），它与 12345 是两个不同的学号。

输入格式

• 第一行：一个整数 n，表示学生数；
• 接下来 n 行：每行 id name a b c，学号互不相同；
• 接下来一行：一个整数 m，表示查询次数；
• 接下来 m 行：每行一个学号。

输出格式

共 m 行，每行依次对应一次查询：命中时按上述格式输出整条记录，未命中输出 No Answer!。

数据范围与限制

项目	范围
学生数 n	1 ≤ n ≤ 10⁴
查询数 m	1 ≤ m ≤ 10⁵
学号 id	1 ～ 6 位数字，互不相同，允许前导零
姓名	仅字母，长度 1 ～ 8，不含空格
成绩	0 ≤ a, b, c ≤ 100 的整数
时间复杂度要求	每次查询期望 $O(|id|)$；每次查询都线性扫描全部记录的 $O(nm)$ 做法会在压力用例超时
输出上限	8 MB（判题器放宽了默认 1 MB 输出上限；10⁵ 行命中输出的总长度可超过 1 MB）

正常、边界与错误情况

• 正常：命中的记录原样输出，成绩统一格式化为 1 位小数；
• 边界：n = 1、m = 1；查询顺序与插入顺序不同；1 ～ 6 位不同长度的学号混合；
• 前导零：012345 与 12345 同时存在且互不混淆——把学号转成整数再存取会撞键；
• 未命中：一律输出 No Answer!（注意结尾有感叹号），不允许部分输出或多余空行。

样例

样例 1

3
1001 Alice 78 89 92
1002 Bob 65 70 80
200001 Carol 90 88 76
4
1001
9999
200001
1002

1001 Alice 78.0 89.0 92.0
No Answer!
200001 Carol 90.0 88.0 76.0
1002 Bob 65.0 70.0 80.0

1001、200001、1002 命中，整数成绩被格式化成 1 位小数；9999 不在名册，输出 No Answer!。

样例 2

2
012345 Zoe 60 61 62
12345 Max 59 58 57
3
012345
12345
1

012345 Zoe 60.0 61.0 62.0
12345 Max 59.0 59.0 59.0

012345 与 12345 是两个不同的键：若把学号转成整数当数组下标，它们会落在同一个下标上，Zoe 的记录就会覆盖 Max。查询 1 不存在，输出 No Answer!。

实现提示

两种口径都值得算一算：

• 直接定址：把学号转成整数当数组下标。6 位学号值域到 999999，要开 10⁶ 个单元才保险，而 n 只有 10⁴——装填因子约 0.01，绝大部分空间被浪费；学号位数再多一位、或出现前导零（012345 与 12345 转整数后相同），这套“数组打表”就会越界或撞键。这正是王道书打表解法的适用边界。
• 散列映射：对学号字符串做 131 进制多项式散列，对素数表长（如 20011）取模得到桶下标，链地址法处理冲突；节点存“学号字符串 + 记录下标”，冲突时比较原串。前导零作为字符参与散列，天然安全。

浮点输出用 printf("%.1f", ...) 或 std::fixed << std::setprecision(1)，整数成绩转成 double 再输出。用 std::unordered_map<std::string, int> 做对照可以，但本 Lab 要求提交的手写实现里包含自己的散列函数与冲突处理。

运行

make run
# 免 Make 兜底：在仓库根执行
pnpm lab:run -- labs/chapter-09/exercise/E-09-04-student-record-lookup

需要单用例或严格评分时使用 make run CASE=005-stress-1e4-1e5 与 make score；也可用 pnpm lab:score -- labs/chapter-09/exercise/E-09-04-student-record-lookup 兜底。

完成清单

• 样例 1、样例 2 与 make run 全部用例通过；
• 散列索引核心（字符串散列函数 + 链地址冲突处理 + 原串比较）是手写的；
• 012345 与 12345 这类前导零学号不会撞键，未命中统一输出 No Answer!；
• 压力用例（n = 10⁴、m = 10⁵）在时限内完成，能算清直接定址 10⁶ 单元与散列表 10⁴ 节点的空间差距。

思考与复盘

1. 王道书“数组打表”解法在什么数据范围下是合理的？按“空间开销 = 键值域大小 × 单元大小”算一算 6 位学号的账。
2. 012345 转成整数后与 12345 冲突，这说明“把键数字化”丢失了哪类信息？什么样的键必须按字符串处理？
3. 若 m = 10⁵ 次查询全部集中在同一张表上，“先排序再二分”与散列表如何取舍？可对照教材“散列表与有序结构的取舍”一节。