题解 [SCOI2005]王室联邦
2022/8/11 6:27:11
本文主要是介绍题解 [SCOI2005]王室联邦,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
之前树分块也只是听说,今天亲手学了一下(?)(
首先你会发现这个 \(B\) 和 \(3B\) 的约束就很迷(我也不知道为什么搞这种奇怪的约束(悲)),学了才知道。。。
所以这题的分块方法好像叫“王室联邦分块法”。
可还行~
不吹水了,来口胡一波。
首先明确一点,任何一个省会一定是一群节点的祖先。
因此我们可以考虑将一棵树的一个节点断掉然后不断递归这样是没法处理的,我们考虑王室联邦分块法可还行。DFS 整棵树,对于每个节点 \(u\),遍历所有儿子 \(v\)。我们先设有一个栈 \(sta\)。当我们在做的时候,如果新加的元素超过 \(b\) 个我们就新开一个省,把 \(u\) 作为省会,然后把栈刚刚加过的 \(b\) 个元素弹出来。最后我们还要将 \(u\) 入栈,返回上一层。
DFS 完可能剩下一些点,我们把它丢进以根为省会的省中。
这个过程是不是很简单?我们考虑这个算法的合法性。
每个点顶多会有 \(b\) 个,它的儿子的点就得减去它本身,\(b - 1\) 个,也就是说 \(sta\) 任意时刻不可能大小超过 \(2b - 1\)。
剩下的 \(sta\) 顶多 \(b\) 个,根顶多 \(2b - 1\) 个,最终顶多 \(3b - 1\) 个,合法。
其实感觉自己理解的有点不太到位啊,明天再填坑,如果有纰漏 QQ 撅我,QQ 2392303708
//SIXIANG #include <iostream> #include <vector> #define MAXN 100000 #define QWQ cout << "QWQ" << endl; using namespace std; vector <int> gra[MAXN + 10]; int sta[MAXN + 10], top = 0; int cap[MAXN + 10], bel[MAXN + 10], cnt = 0; int n, b; void dfs(int u, int fa) { int now = top; for(int p = 0; p < gra[u].size(); p++) { int v = gra[u][p]; if(v != fa) { dfs(v, u); if(top - now >= b) { cap[++cnt] = u; while(top != now) bel[sta[top--]] = cnt; } } } sta[++top] = u; } int main() { cin >> n >> b; for(int p = 1, x, y; p < n; p++) { cin >> x >> y; gra[x].push_back(y); gra[y].push_back(x); } dfs(1, 0); while(top) bel[sta[top--]] = cnt; cout << cnt << endl; for(int p = 1; p <= n; p++) cout << bel[p] << ' '; cout << endl; for(int p = 1; p <= cnt; p++) cout << cap[p] << ' '; }
这篇关于题解 [SCOI2005]王室联邦的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升