十滴水

GitHub跳转原题关系图 Canvas 关系图返回列表

用有序映射维护有水格子，用最小堆按编号处理爆炸，并在爆炸时更新当前前驱和后继。

OJ: shumeng

题目 ID: CSP202403D

难度:普及+/提高-

标签:模拟有序集合优先队列

日期: 2026-07-31 16:21

形式化题目

一维网格 $1 \sim c$ 中部分格子有 $1 \sim 4$ 滴水。共 $n$ 次操作，每次给指定格子加一滴水：

若某格子达到 $5$ 滴，它立刻清空，并让当前时刻它左右两侧最近的有水格子各加一滴水；
多个格子同时待爆炸时，按位置从小到大依次爆炸，且新产生的爆炸按相同规则加入待爆序列。

每次操作结束后输出仍有水的格子数。

思路

这题是带连锁反应的模拟，核心要支持两类操作：找出当前格子左右最近的有水格子，以及按位置顺序处理待爆格子。

朴素做法：有序数组暴力模拟

先看一个直觉做法：把所有有水的格子放进排序数组，每次爆炸用二分找位置、删掉它再给相邻元素加水。

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，用有序数组保存有水格子，二分查找相邻格子。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int c, m, operation_count;
    cin >> c >> m >> operation_count;
    vector<pair<int, int> > water; // water[i] = {位置, 水滴数}，按位置升序排列
    for (int i = 0; i < m; i++) {
        pair<int, int> current;
        cin >> current.first >> current.second;
        water.push_back(current);
    }
    sort(water.begin(), water.end());

    while (operation_count--) {
        int position;
        cin >> position;
        vector<int> exploding; // 待爆炸的位置列表
        // 找到指定位置并加一滴水
        for (int i = 0; i < (int)water.size(); i++) {
            if (water[i].first == position) {
                water[i].second++;
                if (water[i].second >= 5) exploding.push_back(position);
                break;
            }
        }

        while (!exploding.empty()) {
            sort(exploding.begin(), exploding.end()); // 最左的格子先爆
            int current = exploding[0];
            exploding.erase(exploding.begin());

            // 二分找到当前格子在数组中的下标
            vector<pair<int, int> >::iterator current_it = lower_bound(
                water.begin(), water.end(), make_pair(current, -1));
            if (current_it == water.end() || current_it->first != current
                    || current_it->second < 5) continue; // 已被之前的爆炸清空

            int index = current_it - water.begin();
            water.erase(water.begin() + index);

            // 左右相邻的有水格子各加一滴水
            if (index - 1 >= 0) {
                water[index - 1].second++;
                if (water[index - 1].second >= 5) exploding.push_back(water[index - 1].first);
            }
            if (index < (int)water.size()) {
                water[index].second++;
                if (water[index].second >= 5) exploding.push_back(water[index].first);
            }
        }

        cout << water.size() << '\n';
    }

    return 0;
}

这个做法每步的数组删除是 $O(m)$ 的，只适合小数据，但能帮助验证连锁反应的规则。

主解：map 维护相邻 + 小根堆维护爆炸顺序

用 map<位置, 水滴数> 保存所有有水格子，有序键天然给出“左右相邻的有水格子”。一次爆炸时，先记住当前格子的前驱和后继迭代器，再删除当前格子，这样取到的正是爆炸瞬间两侧最近的格子。

待爆炸位置放进小根堆，保证每次处理编号最小的格子。堆里可能出现已被之前爆炸清空的过期位置，弹出时检查它是否仍在 map 中且水滴数 $\ge 5$ ，不满足就跳过。

关键性质：一个格子爆开后从有水集合中消失，本轮不会再被重新加入，所以所有爆炸的总次数是 $O(m)$ 的。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

map<int, int> water;  // water[pos] 表示位置 pos 当前的水滴数，只保存有水的格子
priority_queue<int, vector<int>, greater<int> > exploding; // 待爆炸位置，小根堆保证最左的先爆

// 给位置 pos 加一滴水，达到 5 滴就加入待爆堆
void add_water(int pos) {
    water[pos]++;
    if (water[pos] >= 5) exploding.push(pos);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int c, m, operation_count;
    cin >> c >> m >> operation_count;
    for (int i = 0; i < m; i++) {
        int pos, cnt;
        cin >> pos >> cnt;
        water[pos] = cnt;
    }

    while (operation_count--) {
        int position;
        cin >> position;
        add_water(position);

        // 处理连锁爆炸，直到没有待爆格子
        while (!exploding.empty()) {
            int current = exploding.top();
            exploding.pop();
            map<int, int>::iterator it = water.find(current);
            if (it == water.end() || it->second < 5) continue; // 已被之前的爆炸清空

            // 先记住左右相邻的有水格子，再删除当前格子
            map<int, int>::iterator left = it;
            bool has_left = (left != water.begin());
            if (has_left) --left;
            map<int, int>::iterator right = it;
            ++right;
            bool has_right = (right != water.end());
            water.erase(it);

            if (has_left) add_water(left->first);
            if (has_right) add_water(right->first);
        }

        cout << water.size() << '\n';
    }

    return 0;
}

复杂度

设 $m$ 为初始有水格子数， $n$ 为操作数。

时间：每个格子至多爆炸一次，每次 map 查找与更新 $O(\log m)$ ，总时间复杂度 $O((n + m) \log m)$ 。
空间：map 中最多 $m$ 个格子，空间复杂度 $O(m)$ 。

总结

模拟连锁反应时要把握两个关键数据结构：有序集合表达“最近的有水格子”，优先队列表达“多个待爆格子按最左优先”。删除当前节点后再取邻居，能避免把已经清空的格子当成传播目标；堆中残留的过期元素通过合法性检查丢弃即可。

题目来自第 33 次 CSP 认证 T4，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： ~~3.0 秒~~ 1.0 秒

空间限制： 512 MB

题目描述

十滴水是一个非常经典的小游戏。

小 C 正在玩一个一维版本的十滴水游戏。我们通过一个例子描述游戏的基本规则。

游戏在一个 $1 \times c$ 的网格上进行，格子用整数 $x(1 \leq x \leq c)$ 编号，编号从左往右依次递增。网格内 $m$ 个格子里有 $1 \sim 4$ 滴水，其余格子里没有水。在我们的例子中， $c=m=5$ ，按照编号顺序，每个格子中分别有 $2,4,4,4,2$ 滴水。

玩家可以进行若干次操作，每次操作中，玩家选择一个有水的格子，将格子的水滴数加一。任何时刻若某个格子的水滴数大于等于 $5$ ，这个格子里的水滴就会向两侧爆开。此时，这个格子的水被清空，同时对于左方、右方两个方向同时进行以下操作：找到当前格子在对应方向上最近的有水的格子，如果存在这样的格子，将这个格子的水滴数加一。若在某个时刻，有多个格子的水滴数大于等于 $5$ ，则最靠左的先爆开。

在我们的例子中，若玩家对第三格进行操作，则其水滴数变为 $5$ ，故第三格水滴爆开，水被清空，其左侧最近的有水格子（第二格）和右侧最近的有水格子（第四格）的水量增加 $1$ ，此时每个格子中分别有 $2,5,0,5,2$ 滴水。

此时第二格和第四格的水滴数均大于等于 $5$ ，按照规则，第二格的水先爆开，爆开后每个格子中分别有 $3,0,0,6,2$ 滴水；最后第四格的水滴爆开，每个格子中分别有 $4,0,0,0,3$ 滴水。

小 C 开始了一局游戏并进行了 $n$ 次操作。小 C 在每次操作后，会等到所有水滴数大于等于 $5$ 的格子里的水滴都爆开再进行下一次操作。

小 C 想知道他的水平有多高，于是他想知道每一次操作后还有多少格子里有水。

保证这 $n$ 次操作都是合法的，即每次操作时操作的格子里都有水。

输入格式

从标准输入读入数据。

输入的第一行三个整数 $c,m,n$ 分别表示网格宽度、有水的格子个数以及操作次数。

接下来 $m$ 行每行两个整数 $x, w$ ，表示第 $x$ 格有 $w$ 滴水。

接下来 $n$ 行每行一个整数 $p$ ，表示小 C 对第 $p$ 格做了一次操作。

输出格式

输出到标准输出。

输出 $n$ 行，每行一个整数表示这次操作之后网格上有水的格子数量。

input1

output1

1
22
1

子任务

对于所有测试数据，

$1 \leq c \leq 10^9$ ， $1 \leq m \leq \min(c, 3 \times 10^5)$ ， $1 \leq n \leq 4m$ ；
$1 \leq x, p \leq c$ ， $1 \leq w \leq 4$ ；
输入的所有 $x$ 两两不同；
对于每个输入的 $p$ ，保证在对应操作时 $p$ 内有水。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	$c\le$	$m\le$	特殊性质	分值
1	$30$	$30$	$\checkmark$	15
2	$3000$	$3000$	$\checkmark$	15
3	$3000$	$3000$	$\times$	10
4	$10^9$	$3000$	$\times$	15
5	$3\times 10^5$	$3\times 10^5$	$\times$	15
6	$10^9$	$3\times 10^5$	$\checkmark$	15
7	$10^9$	$3\times 10^5$	$\times$	15

特殊性质：在游戏的任意时刻（包括水滴爆开的连锁反应过程中），只有至多一个格子的水滴数大于等于 $5$ 。

提示

本题输入输出量较大，请采用效率较高的输入输出方式。

十滴水

目录

形式化题目

思路

朴素做法：有序数组暴力模拟

主解：map 维护相邻 + 小根堆维护爆炸顺序

代码

复杂度

总结