十滴水游戏

题目简述一、游戏设定网格长度c1×c 的一维网格格子编号 1~c初始有m个格子有水水量 1~4其他格子没水操作玩家选择有水的格子p将其水量 1二、爆炸规则当一个格子水量≥5时该格子清空水消失同时向左右两侧找到最近的有水格子各 1 水如果有多个格子同时 ≥5按从左到右的顺序依次爆炸三、连锁反应一个格子爆炸可能使邻居水量达到 ≥5引发新的爆炸直到没有格子水量 ≥5本轮操作结束四、输入输出输入第一行c m n网格长度、有水的格子数、操作次数接下来m行x w位置 x 有 w 滴水接下来n行p每次操作的位置输出每行一个整数每次操作后还有水的格子数量五、数据范围c最大 10^9很大不能开数组m最大 3×10^5有水的格子数n最大 4m ≈ 1.2×10^6操作次数同步关闭ios::sync_with_stdio(false); cin.tie(nullptr);map和unordered_map1.map有序映射基于红黑树实现元素按key 自动排序升序查找、插入、删除O(log n)2.unordered_map无序映射基于哈希表实现元素无序存储查找、插入、删除平均O(1)最坏 O(n)//初始化 // map mapint, string m1; mapint, string m2 {{1, one}, {2, two}, {3, three}}; // unordered_map unordered_mapint, string um1; unordered_mapint, string um2 {{1, one}, {2, two}, {3, three}}; //插入 // 方式1用 [] 运算符 m[5] five; um[5] five; // 方式2insert 函数 m.insert({4, four}); um.insert({4, four}); // 方式3insert 带判断 auto result m.insert({6, six}); if (result.second) { cout 插入成功 endl; } //访问 // 用 [] 运算符如果key不存在会创建 string s1 m[1]; // 存在返回value string s2 m[100]; // 不存在创建空字符串 // 用 at() 函数如果key不存在抛出异常 try { string s m.at(100); } catch (const out_of_range e) { cout key不存在 endl; } //查找 // find 返回迭代器找不到返回 end() auto it m.find(3); if (it ! m.end()) {//m.end() 返回一个指向容器末尾之后位置的迭代器通常称为尾后迭代器。 cout 找到了 it-first - it-second endl; } else { cout 没找到 endl; } // count 返回元素个数对于map只能是0或1 if (m.count(3) 0) { cout key 3 存在 endl; } //删除 // 按key删除 m.erase(3); um.erase(3); // 按迭代器删除 auto it m.find(5); if (it ! m.end()) { m.erase(it); } //遍历 // 范围for循环 for (auto p : m) { // p 是容器中的元素本身引用 // 直接修改原数组 // p 的类型是 pairconst int, string cout p.first : p.second endl; } // 迭代器循环 for (auto it m.begin(); it ! m.end(); it) { // it 是迭代器指向元素 // *it 才是元素本身 cout it-first : it-second endl; }setset是 C 中的有序集合特点自动排序默认升序、元素唯一无重复、基于红黑树实现、查找、插入、删除O(log n)//定义和初始化 // 空set setint s1; // 初始化列表 setint s2 {5, 2, 8, 2, 1}; // 实际存储1,2,5,8自动排序去重 // 复制构造 setint s3(s2); // 指定排序规则降序 setint, greaterint s4 {5, 2, 8, 1}; // 存储8,5,2,1 // 自定义排序 struct cmp { bool operator()(int a, int b) const { return a b; // 降序 } }; setint, cmp s5; //插入 setint s; // 1. insert() 插入单个元素 s.insert(5); s.insert(3); s.insert(7); s.insert(5); // 重复插入无效 // s 现在是3,5,7 // 2. insert() 返回pairiterator, bool auto result s.insert(4); if (result.second) { cout 插入成功 endl; } else { cout 元素已存在 endl; } // 3. insert() 插入范围 vectorint v {1, 8, 6}; s.insert(v.begin(), v.end());//v.end() 指向的是最后一个元素的下一个位置尾后位置。 // 4. emplace() 直接构造效率更高 s.emplace(9); // 相当于 s.insert(9) //删除 setint s {1, 2, 3, 4, 5}; // 1. erase(值) s.erase(3); // 删除元素3 // s: 1,2,4,5 // 2. erase(迭代器) auto it s.find(2); if (it ! s.end()) { s.erase(it); // 删除迭代器指向的元素 } // 3. erase(范围) auto start s.find(4); auto end s.find(5); if (start ! s.end() end ! s.end()) { s.erase(start, end); // 删除[4,5] } // 4. clear() 清空 s.clear(); // 5. 遍历时删除 for (auto it s.begin(); it ! s.end(); ) { if (*it % 2 0) { it s.erase(it); // erase返回下一个迭代器 } else { it; } } //查找 setint s {10, 20, 30, 40, 50}; // 1. find() - 返回迭代器 auto it s.find(30); if (it ! s.end()) { cout 找到了: *it endl; } else { cout 没找到 endl; } // 2. count() - 返回元素个数0或1 if (s.count(20) 0) { cout 20存在 endl; } // 3. contains() - C20 if (s.contains(40)) { cout 40存在 endl; } // 4. lower_bound() - 第一个 key 的元素 auto it1 s.lower_bound(25); // 指向30 // 5. upper_bound() - 第一个 key 的元素 auto it2 s.upper_bound(30); // 指向40 // 6. equal_range() - 返回范围 [lower_bound, upper_bound) auto range s.equal_range(30); // range.first 指向30 // range.second 指向40 //遍历 setint s {5, 2, 8, 1, 3}; // 1. 范围for循环最常用 for (int x : s) { cout x ; // 输出1 2 3 5 8 } // 2. 迭代器循环 for (auto it s.begin(); it ! s.end(); it) { cout *it ; } // 3. 反向遍历 for (auto it s.rbegin(); it ! s.rend(); it) { cout *it ; // 输出8 5 3 2 1 } // 4. 修改元素不行set的元素是const for (int x : s) { // 错误set的元素不能修改 x 100; // 编译错误 } //查找特定元素 setint s {1, 2, 3, 4, 5}; // 大小 cout s.size() endl; // 5 cout s.empty() endl; // 0 (false) // 最大/最小元素 cout *s.begin() endl; // 1最小 cout *s.rbegin() endl; // 5最大 cout *s.end() endl; // 错误end()是尾后迭代器 // 获取第一个元素安全做法 if (!s.empty()) { int first *s.begin(); int last *s.rbegin(); } // 获取第k个元素set不支持随机访问 // int kth s[2]; // 错误set不能用下标queuequeue是 C 中的队列容器先进先出FIFOFirst In First Out的数据结构//定义和初始化 // 定义空队列 queueint q; // 定义存放字符串的队列 queuestring q2; // 定义存放自定义类型的队列 struct Person { string name; int age; }; queuePerson q3; // 不能直接初始化列表需要先有容器 // queueint q {1, 2, 3}; // 错误 //核心操作 queueint q; // 1. push() - 入队在队尾插入 q.push(10); q.push(20); q.push(30); // 队列现在10 20 30左边是队首 // 2. front() - 访问队首元素 cout q.front(); // 输出 10 // 3. back() - 访问队尾元素 cout q.back(); // 输出 30 // 4. pop() - 出队删除队首元素 q.pop(); // 删除10 // 队列现在20 30 // 5. empty() - 判断是否为空 if (q.empty()) { cout 队列为空 endl; } // 6. size() - 获取大小 cout q.size(); // 输出 2完整代码#includebits/stdc.h using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int c,m,n; cincmn; unordered_mapint,int ma; setint poses; for(int i0;im;i){ int x,w; cinxw; ma[x]w; poses.insert(x); } for(int i0;in;i){ int p; cinp; ma[p]; if(ma[p] 5){ queuesetint::iterator q; // 用queue存迭代器 auto it poses.find(p); // 处理第一次爆炸 auto it1 it, it2 it; if(it ! poses.begin()) it1--; it2; if(it ! poses.begin()) ma[*it1]; if(it2 ! poses.end()) ma[*it2]; if(it ! poses.begin() ma[*it1] 5) q.push(it1); else if(it2 ! poses.end() ma[*it2] 5) q.push(it2); ma[p] 0; // 清空水量 poses.erase(it); // 处理连锁爆炸 while(!q.empty()){ auto nextp q.front(); q.pop(); auto it1 nextp, it2 nextp; if(nextp ! poses.begin()) it1--; it2; if(nextp ! poses.begin()) ma[*it1]; if(it2 ! poses.end()) ma[*it2]; ma[*nextp] 0; if(nextp ! poses.begin() ma[*it1] 5) q.push(it1); else if(it2 ! poses.end() ma[*it2] 5) q.push(it2); poses.erase(nextp); } } cout poses.size() \n; } return 0; }