CF1620E - Replace the Numbers(构造算法 + 数据结构 + 并查集 + 模拟 / 铁牌级)
2022/1/19 1:07:03
本文主要是介绍CF1620E - Replace the Numbers(构造算法 + 数据结构 + 并查集 + 模拟 / 铁牌级),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1620E - Replace the Numbers(源地址自⇔CF1620E)
目录- 1620E - Replace the Numbers(源地址自⇔CF1620E)
- tag
- 题意
- 思路
- AC代码
- 错误次数
tag
⇔构造算法、⇔数据结构、⇔并查集、⇔模拟、⇔铁牌级(*1900)
题意
给出一个空数组,规定两种操作:
- 在数组末尾加上 \(x\) ;
- 将数组中全部的 \(x\) 替换为 \(y\) 。
现在有 \(q\) 次询问,请输出结果数组。
思路
首先考虑暴力的做法,一旦遇到第二种操作,便从头遍历一遍数组。显然这会超时,但我们发现,第二种操作是无后效性的,我们考虑倒序操作数组。
倒序思考的话就很简单了:遇到第二种操作便建立(更新)一个映射,遇到第一种操作就将读入的 \(x\) 所对应的映射加入数组。这一过程就像并查集找祖先一样,但其实不然——刚刚提到,第二种操作是无后效性的,直接使用并查集的话会破坏原有的顺序,导致产生后效性。
这里其实比较绕,不太容易说清,尝试小小的总结一下:并查集是一路回溯寻找祖先;而本题由于逆序操作,映射是不断在更新的,回溯一轮即得到结果。参见下方 \(\tt{hack}\) 数据。
点击查看数据样例
4
1 2
2 6 2
2 3 1
2 2 3如本例,在读入第二组数据时,并查集搜索 \(2\) 的父亲: \(3\) 。依照无后效性原则,此时应当结束搜索,但是由于已知 \(3\) 的父亲为 \(1\) ,故并查集会将 \(2\) 链接至 \(1\) 。
AC代码
点击查看代码
//==================== LL n, ans, num, fa[MAX], x[MAX], y[MAX], k[MAX]; bool Ans; vector<int> v; //==================== void Clear() { ans = 0; Ans = true; } void Solve() { cin >> n; FOR(i, 1, n) { cin >> k[i] >> x[i]; if(k[i] == 2) cin >> y[i]; } FOR(i, 1, MAX - 2) fa[i] = i; FORD(i, 1, n) { if(k[i] == 2) fa[x[i]] = fa[y[i]]; else v.push_back(fa[x[i]]); } reverse(v.begin(), v.end()); for(auto it : v) cout << it << " "; }
错误次数
文 / WIDA
2022.01.18 成文
首发于WIDA个人博客,仅供学习讨论
更新日记:
2022.01.18 成文
这篇关于CF1620E - Replace the Numbers(构造算法 + 数据结构 + 并查集 + 模拟 / 铁牌级)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享