启发式合并和DSU on tree入门
2022/8/11 6:27:10
本文主要是介绍启发式合并和DSU on tree入门,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
启发式合并
定义
一个基于直观或经验构造的算法,在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度一般不能被预计。
举个栗子:并查集的按秩合并。
每次我们将大集合合并到小集合里,新集合至少为大集合的两倍,每次合并都会变大为两倍,每个元素至多经过 \(log(n)\)次合并,时间复杂度更优秀。
void merge(int x, int y) { int rx = find(x), int ry = find(y); if (sz[rx] < sz[ry]) swap(rx, ry); f[ry] = rx; sz[rx] += ry; }
例题-梦幻布丁
题目描述
\(n\) 个布丁摆成一行,进行 \(m\) 次操作。每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色。
例如,颜色分别为 \(1,2,2,1\) 的四个布丁一共有 \(3\) 段颜色.
输入格式
第一行是两个整数,分别表示布丁个数 \(n\) 和操作次数 \(m\)。
第二行有 \(n\) 个整数,第 \(i\) 个整数表示第 \(i\) 个布丁的颜色 \(a_i\)。
接下来 \(m\) 行,每行描述一次操作。每行首先有一个整数 \(op\) 表示操作类型:
- 若 \(op = 1\),则后有两个整数 \(x, y\),表示将颜色 \(x\) 的布丁全部变成颜色 \(y\)。
- 若 \(op = 2\),则表示一次询问。
思路
-
如何快速求出改变后的段数
求出起始段数,之后每次改变前先把原先的贡献减掉,再加上变化后的贡献。
-
如何将大集合合并到小集合里
把x颜色变成y和把y颜色变成x颜色是等价的,但是在变色过程中要保持一致,x颜色变成y颜色。
代码实现
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 101000; const int M = 1010000; int n, m, a[N], ans; vector<int> pos[M]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); pos[a[i]].push_back(i); } for (int i = 1; i <= n + 1; i++) { ans += a[i] != a[i - 1]; } for (int i = 0; i < m; i++) { int op; scanf("%d", &op); if (op == 2) { printf("%d\n", ans - 1); } else { int x, y; scanf("%d%d", &x, &y); if (x == y) continue; if (pos[x].size() > pos[y].size()) { pos[x].swap(pos[y]); // O(1) // swap(pos[x], pos[y]); O(1) } if (pos[y].empty()) continue; auto modify = [&](int p, int col) { ans -= (a[p] != a[p - 1]) + (a[p] != a[p + 1]); a[p] = col; ans += (a[p] != a[p - 1]) + (a[p] != a[p + 1]); }; int col = a[pos[y][0]]; for (int p : pos[x]) { modify(p, col); pos[y].push_back(p); } pos[x].clear(); } } }
DSU On Tree
定义
树上启发式合并(dsu on tree)对于某些树上离线问题可以速度大于等于大部分算法且更易于理解和实现的算法,本质还是启发式合并的思想。
重儿子 | 一个结点的所有儿子中拥有最多子树的儿子 |
---|---|
轻儿子 | 一个结点的所有儿子中不是重儿子的儿子 |
重边 | 父亲与重儿子的连边 |
轻边 | 父亲与轻儿子的连边 |
重链 | 一堆重边连接而成的链 |
轻链 | 一堆轻边连接而成的链 |
步骤
代码实现
// DFS序减少遍历子树的常数 void dfs_init(int u, int f) { l[u] = ++tot; id[tot] = u; sz[u] = 1; hs[u] = -1; for (auto v : e[u]) { if (v == f) continue; dfs(v, u); sz[u] += sz[v]; if (hs[u] == -1 || sz[v] > sz[hs[u]]) hs[u] = v; } r[u] = tot; } void dfs_solve(int u, int f, bool keep) { for (auto v : e[u]) if (v != f && v != hs[u]) dfs(v, u, false); if (hs[2] != -1) dfs(hs[u],u,true); // 把轻儿子加入到重儿子里 for (auto v : e[u]) if (v != f && v != hs[u]) rep(x, l[v], r[v]) add[id[x]]; // u 本身加入 add(u); // keep 是否需要保留信息 if (!keep) rep(i,l[u],r[i]) del[id[x]]; }
这篇关于启发式合并和DSU on tree入门的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行