CF1303F 题解
2024-09-08 18:53:25
题意
有一个 \(n\times m\) 的矩阵，初始全是 \(0\)。我们定义 \(a_{i,j}\) 表示矩阵中第 \(i\) 行第 \(j\) 列的元素。
如果两个格子有相邻边并且格子中的元素相同，我们就说它们是联通的。联通关系可以传递，也就是说整个矩阵被分成了若干个联通块。
你需要处理 \(q\) 次修改操作，第 \(i\) 次操作包含三个整数 \(x_i,y_i,c_i\)，表示将 \(a_{x_i,y_i}\) 替换为 \(c_i\)。每次修改结束后你需要求出这个矩阵当前有多少连通块。
\(1\le n,m\le 300,1\le q\le 2\times 10^6,1\le c_i\le \max(1000,\lceil\frac{2\times 10^6}{nm}\rceil),c_i\le c_{i+1}(i\in [1,q-1])\)
题解
动态图连通性板题，于是做完了
我们将一次修改操作（将 \(a_{x,y}\) 从 \(z\) 改为 \(w\)）分为两步考虑：在\(w\) 的导出子图中加入 \(a_{x,y}\)，在 \(z\) 的导出子图中删除 \(a_{x,y}\)。加入操作可以用并查集，但删除操作不好处理。但由于此题的特殊性质，\(z\) 一定小于 \(w\)（这里不考虑相等的情况）。我们考虑规避删除。
逆着做一遍。那么就是将 \(w\) 改为 \(z\)。此时，在 \(z\) 的导出子图中加入 \(a_{x,y}\) 增加的连通块个数与 上段操作中在 \(z\) 的导出子图中删除 \(a_{x,y}\) 增加的连通块个数互为相反数。正确性易证。于是此题得解。
最新文章
- js正则表达式校验非零的正整数：^[1-9]\d*$ 或 ^([1-9][0-9]*){1,3}$ 或 ^\+?[1-9][0-9]*$
- Effective C++ -----条款14: 在资源管理类中小心copying行为
- C++ 不能在类体外指定关键字static
- java笔记1
- Moodle插件之Filters（过滤器）
- 千份位Javascript Thousand Separator / string format
- HBase的数据迁移（含HDFS的数据迁移）
- 大数据导入Excel
- [转载]字典树(trie树)、后缀树
- 解决关于IIS10.0下无法安装 URL 重写模块 2的问题
- SQL serve创建与调用存储过程
- Asp.Net异步编程
- G - Zombie’s Treasure Chest（动态规划专项）
- 关于JAVASCRIPT call 方法和 apply 方法性能对比
- 合理使用软引用和弱引用，提升JVM内存使用性能
- 推荐一个c++小巧开源且跨平台的图像解码库
- ES6语法的学习与实践
- 在Windows系统上一批可以下载但是需要经过编译再安装的第三方的直接编译后的版本（UCI页面）
- [leetcode]Candy @ Python
- Java数据结构和算法（四）：栈