1 条题解

  • 0
    @ 2026-11-16 20:48:26

    稀疏棋盘 · 讲解

    思路与接口

    用 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
    上传者