1 条题解
-
0
稀疏棋盘 · 讲解
思路与接口
用
map<pair<int,int>,long long>保存棋盘。pair的两个字段按顺序保存行、列,不能交换,也不能只用其中一个字段作 key。SET 使用
board[{r,c}]=v,包括 v=0 的情况。GET 调用find({r,c}),只根据是否返回end()判断是否存在。ERASE 调用erase({r,c}),直接输出返回值 0 或 1。COUNT 输出size()。正确性
pair 的相等要求两个字段分别相等,与题目的坐标定义一致。每个 SET 都在且只在目标坐标写入值;覆盖不会重复保存坐标。查询读取已保存的 value,删除只移除目标 key,计数返回 key 的数量,所以全部操作和输出正确。
复杂度
每次 SET、GET、ERASE 为 O(log q),COUNT 为 O(1),总时间 O(q log q),空间 O(q)。坐标可为负,不适合按最大坐标开二维数组。
常见错误
- 把 0 当作未保存或删除标志。这会让 GET、COUNT、ERASE 同时出错;配套错误程序在 SET 为 0 时执行删除。
- 查询时使用
operator[],意外插入缺失坐标。 - 忽略行列顺序,把 (1,2) 与 (2,1) 合并。
- 用不充分的字符串拼接或整数乘法编码坐标,造成碰撞或溢出。pair 不需要这种编码。
数据验证说明
Python 使用二元组作为字典键,明确区分“key 不存在”和“key 存在且值为 0”。样例与最大零值数据均覆盖这种差异,并检查负坐标、整数边界和重复删除。
原创来源记录
本题题面、样例、代码、讲解与数据从零编写。只使用公开的算法概念和 C++ 标准库接口,没有使用第三方题面、故事、程序或测试文件。
C++17 参考实现
#include <iostream> #include <map> #include <string> #include <utility> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; map<pair<int, int>, long long> board; while (q--) { string op; cin >> op; if (op == "COUNT") { cout << board.size() << '\n'; } else { int r, c; cin >> r >> c; pair<int, int> key = {r, c}; if (op == "SET") { long long value; cin >> value; board[key] = value; } else if (op == "GET") { auto it = board.find(key); if (it == board.end()) cout << "EMPTY\n"; else cout << it->second << '\n'; } else { cout << board.erase(key) << '\n'; } } } }
- 1
信息
- ID
- 5264
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者