装修找什么平台比较好_公关策划书模板范文_公众号微博seo_外链官网

题干：

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

小 $C$ 正在玩一个一维版本的十滴水游戏。

我们通过一个例子描述游戏的基本规则。

游戏在一个 $1\times c$ 的网格上进行，格子用整数 $x(1\le x\le 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$ 行，每行一个整数表示这次操作之后网格上有水的格子数量。

数据范围

对于所有测试数据，

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

子任务编号

$c\le$

$m\le$

特殊性质

$1$

$30$

$30$

有

$2$

$3000$

$3000$

有

$3$

$3000$

$3000$

无

$4$

$10^9$

$3000$

无

$5$

$3\times 10^5$

$3\times 10^5$

无

$6$

$10^9$

$3\times 10^5$

有

$7$

$10^9$

$3\times 10^5$

无

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

输入样例：

5 5 2
1 2
2 4
3 4
4 4
5 2
3
1

输出样例：

2
1

这道题读完题就明白我们要使用双链表。因为我们可以很容易地看到水槽里面没有水的格子是没有用的，可以直接删去（题干中每次加水只在左右两边的第一个有水的格子），而且我们要能够访问每一个格子它的左右两边的格子。我们明显还要使用到map<>, 因为可以明显的看见对于给定的每一个序号我们能够得到他的水的滴数。所以我们可以想到要使用map<int , Node*> Node是爽两边节点。

下面代码里面有注释，欢迎又不懂的在评论区留言

#include <bits/stdc++.h>using namespace std;const int N = 3e5 + 5;
map<int,int> h; 
// 使用map来进行排序，unordered_map来进行存储
// 题目中样例给的下标是有序的，但是题目中没有说一定是有序的，所以有可能是无序的要先排序。struct Node {int num;Node * left;Node * right;
};int main() {int c, m, n;scanf("%d%d%d", &c, &m, &n);for (int i = 0; i < m; i++) {int a,b;scanf("%d%d", &a, &b);h[a] = b;}unordered_map<int,Node*> s;// 里面放Node指针，就可以指向map里面存储的节点。Node* node = nullptr;for(auto it = h.begin() ; it != h.end() ; it++){//存入unordered_map，记录双链表信息//指针的调用要用 ->Node* new_node = new Node;new_node->num = it->second;new_node->left = node;new_node->right = nullptr;s[it->first] = new_node;if(it != h.begin())node -> right = new_node;node = new_node;}int msize = m;for (int i = 0; i < n; i ++ ){int k;scanf("%d" , &k);node = s[k];node->num ++ ;if(node->num > 4) {while(node){if(node->left){node->left->num ++;node->left->right = node->right;}if(node ->right){node->right->num ++ ;node->right->left = node->left;}msize -- ;if(node->left && node -> left -> num >4){node = node -> left; continue;}if(node->right && node -> right -> num > 4){node = node -> right;continue;}break;}}printf("%d\n" , msize);}return 0;
}