Ginkgo
True love prevails.
整体难度中等偏下,第二题模拟有点麻烦。三道题分别考察模拟、字符串解析和图论 BFS。题目描述比较贴近实际业务场景,读题需要耐心,但思路都不算复杂。
1. 生日礼物统计
原题
公司每月要为当月生日的同事准备生日礼物,由小明负责统计。给定一个目标月份和员工生日列表,请帮助小明计算该月份需要准备多少份礼物。
规则说明:
- 重复录入的员工生日以最后一次录入为准
- 同一员工不要重复统计
- 名字一致即认为是同一员工(生产系统会通过工号区分,本题简化处理)
输入描述
- 参数 1:要发放礼物的月份 ()
- 参数 2:员工姓名列表(空格分隔)
- 参数 3:员工生日日期列表,与姓名列表一一对应,格式为
Year/Month/Day
输出描述
输出该月份要准备的礼品个数。
样例 1
输入:
1 2 3
| 5 Alice Bob Charlie David Eve Frank Grace Helen 1985/5/10 1990/10/11 1995/10/11 2000/11/10 2005/05/01 2010/10/13 2015/10/14 2020/5/2
|
输出:
说明:5 月份出生的员工有 3 人。
样例 2
输入:
1 2 3
| 5 Alice Bob Charlie Alice Eve Frank Grace Helen 1985/5/10 1990/10/11 1995/10/11 1985/7/10 2005/05/01 2010/10/13 2015/10/14 2020/5/2
|
输出:
说明:Alice 重复录入,第一次是 5 月,第二次是 7 月,以最后一次为准,因此 Alice 不计入 5 月份。
题意概述
给定 个员工的姓名和生日,需要统计指定月份过生日的员工数量。关键点在于同名员工以最后一次录入的生日为准,这意味着需要用哈希表覆盖更新。
思路
- 用
unordered_map<string, string> 存储 姓名 → 生日,后面的录入会自动覆盖前面的
- 遍历哈希表,从每个生日字符串中解析出月份
- 用另一个哈希表统计各月份的人数
- 输出目标月份的人数
时间复杂度:,空间复杂度:
参考实现(C++)
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
| void solve() { int targetMonth; cin >> targetMonth; cin.ignore(); string namesLine, birthsLine; getline(cin, namesLine); getline(cin, birthsLine); stringstream ss1(namesLine), ss2(birthsLine); vector<string> names, births; string token; while (getline(ss1, token, ' ')) names.push_back(token); while (getline(ss2, token, ' ')) births.push_back(token); unordered_map<string, string> nameToBirth; for (size_t i = 0; i < names.size(); ++i) { nameToBirth[names[i]] = births[i]; } unordered_map<int, int> monthCount; for (auto& [name, birth] : nameToBirth) { int p1 = birth.find('/'); int p2 = birth.find('/', p1 + 1); int month = stoi(birth.substr(p1 + 1, p2 - p1 - 1)); monthCount[month]++; } cout << monthCount[targetMonth]; }
|
2. 配置操作失败数量统计
原题
模拟一个系统的命令行配置操作,支持三种命令:
| 命令 |
格式 |
说明 |
add_rule |
add_rule rule_id=X rule_index=Y |
新增规则 |
mod_rule |
mod_rule rule_id=X rule_index=Y |
修改规则 |
del_rule |
del_rule rule_id=X |
删除规则 |
失败判定规则:
- 通用失败:命令关键字非法、缺少必要参数、参数格式错误、参数值不是整数、参数值不在 范围内
add_rule:必须包含 rule_id 和 rule_index;若 rule_id 已存在则失败
mod_rule:必须包含 rule_id 和 rule_index;若 rule_id 不存在或新值与原值相同则失败
del_rule:必须包含 rule_id;若 rule_id 不存在则失败
输入描述
输入为多行字符串,每行包含若干命令,命令之间用空格分隔,总命令数不超过 100 条。
输出描述
输出操作失败的次数。
样例 1
输入:
1 2
| add_rule rule_id=1 rule_index=10 add_rule rule_id=1 rule_index=20
|
输出:
说明:第 1 条成功,第 2 条重复添加失败。
样例 2
输入:
1 2
| add_rule rule_id=1 rule_index=10 mod_rule rule_id=1 rule_index=10
|
输出:
说明:修改前后值相同,判定为失败。
题意概述
这是一道字符串解析 + 状态模拟题。需要解析 key=value 格式的参数,维护一个 rule_id → rule_index 的映射,并根据不同命令的规则判断操作是否成功。
思路
- 将输入按空格分割成 token 序列
- 顺序扫描 token,识别命令关键字(
add_rule/mod_rule/del_rule)
- 收集命令的参数,解析
key=value 格式
- 根据命令类型和当前状态判断是否失败
- 维护
unordered_map<int, int> 存储规则状态
关键点:
- 参数顺序不固定(可能先
rule_index 后 rule_id)
- 需要验证参数格式和取值范围
- 命令之间用空格分隔,需要正确识别命令边界
参考实现(C++)
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
| bool isNumber(const string& s) { if (s.empty()) return false; for (char c : s) if (!isdigit(c)) return false; return true; }
void solve() { string line; getline(cin, line); stringstream ss(line); vector<string> tokens; string token; while (ss >> token) tokens.push_back(token); unordered_map<int, int> rules; int failCount = 0; int i = 0, n = tokens.size(); while (i < n) { string cmd = tokens[i++]; if (cmd != "add_rule" && cmd != "mod_rule" && cmd != "del_rule") { failCount++; continue; } bool hasId = false, hasIdx = false; int id = -1, idx = -1; while (i < n && tokens[i] != "add_rule" && tokens[i] != "mod_rule" && tokens[i] != "del_rule") { string p = tokens[i++]; int pos = p.find('='); if (pos == string::npos) continue; string key = p.substr(0, pos); string val = p.substr(pos + 1); if (!isNumber(val)) continue; int num = stoi(val); if (num < 1 || num > 9999) continue; if (key == "rule_id") { hasId = true; id = num; } else if (key == "rule_index") { hasIdx = true; idx = num; } } if (cmd == "add_rule") { if (!hasId || !hasIdx || rules.count(id)) { failCount++; } else { rules[id] = idx; } } else if (cmd == "mod_rule") { if (!hasId || !hasIdx || !rules.count(id) || rules[id] == idx) { failCount++; } else { rules[id] = idx; } } else if (cmd == "del_rule") { if (!hasId || !rules.count(id)) { failCount++; } else { rules.erase(id); } } } cout << failCount; }
|
3. 直捣黄龙
原题
小王需要潜入敌军阵营实施斩首行动。敌军阵营是一个 的矩阵:
- 入口在坐标
- 敌军司令部在坐标
- 每个哨兵警戒以自己为中心的 9 宫格
- 角色只能上下左右移动,不能斜向
- 需要找到最短路径的条数和路径长度
输入描述
- 参数 1:敌军阵营边长 ( 为大于 1 的奇数,)
- 参数 2:哨兵位置列表,格式为
x,y(行坐标,列坐标),多个坐标空格分隔
输出描述
输出两个整数(空格分隔):最短路径条数、最短路径长度。
样例 1
输入:
输出:
说明:两条最短路径,分别沿左边缘和右边缘绕行。
样例 2
输入:
输出:
说明:哨兵在中心,警戒范围覆盖全图,无可行路径。
题意概述
这是一道带障碍的网格 BFS 最短路计数问题。需要先根据哨兵位置标记所有不可达的格子(9 宫格警戒范围),然后从起点 BFS 到终点,同时统计最短路径的条数。
思路
- 标记障碍:对每个哨兵位置 ,将其 9 宫格范围内的所有格子标记为不可达
- BFS 最短路:从起点 开始 BFS,记录每个格子的最短距离
- 路径计数:在 BFS 过程中,如果某个格子可以通过多条最短路径到达,累加路径数
- 输出结果:终点的路径数和距离
状态转移:
- 第一次到达某个格子:
dist[nx][ny] = dist[x][y] + 1,cnt[nx][ny] = cnt[x][y]
- 以相同最短距离再次到达:
cnt[nx][ny] += cnt[x][y]
时间复杂度:,空间复杂度:
参考实现(C++)
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
| void solve() { int n; cin >> n; cin.ignore(); vector<vector<int>> grid(n, vector<int>(n, 0)); string point; while (cin >> point) { int comma = point.find(','); int sx = stoi(point.substr(0, comma)); int sy = stoi(point.substr(comma + 1)); for (int dx = -1; dx <= 1; dx++) { for (int dy = -1; dy <= 1; dy++) { int nx = sx + dx, ny = sy + dy; if (nx >= 0 && nx < n && ny >= 0 && ny < n) { grid[nx][ny] = -1; } } } } int startX = 0, startY = n / 2; int endX = n - 1, endY = n / 2; vector<vector<int>> dist(n, vector<int>(n, 0)); vector<vector<int>> cnt(n, vector<int>(n, 0)); queue<pair<int, int>> q; q.push({startX, startY}); dist[startX][startY] = 1; cnt[startX][startY] = 1; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (grid[nx][ny] == -1) continue; if (dist[nx][ny] == 0) { dist[nx][ny] = dist[x][y] + 1; cnt[nx][ny] = cnt[x][y]; q.push({nx, ny}); } else if (dist[nx][ny] == dist[x][y] + 1) { cnt[nx][ny] += cnt[x][y]; } } } cout << cnt[endX][endY] << ' ' << dist[endX][endY]; }
|
小结
这三题的难度梯度比较合理。
做题建议:
- 先读透题意:OD 的题目描述通常比较长,包含很多业务场景的包装,需要耐心提取核心规则
- 边界条件要细:尤其是第 2 题的参数校验,各种失败情况要覆盖完整
- BFS 计数是经典模型:第 3 题的路径计数方法在机试中经常出现,值得熟练掌握
整体来说,这套题对基础扎实的同学比较友好,没有特别刁钻的算法,主要考察代码实现能力和细节处理。