LCT 练习记录

作者: wjyyy 分类: LCT,记录篇 发布时间: 2019-01-05 16:17

点击量:49

LCT的题目难度从模板到各种神奇科技有很多级别。

LCT的代码确实好写,不过细节需要特别注意。初学的时候还是背着吧

题目来源

感谢这位老鸽的题单。

Link Cut Tree 总结 – 饕餮传奇

感谢学习笔记非常详细,并热心解答我疑问的FlashHu。

LCT总结——应用篇(附题单)(LCT)- FlashHu

感谢YangZhe的论文。

QTREE解法的一些研究

模板

模板

洛谷 P3690 【模板】Link Cut Tree (动态树)

LCT的所有基础操作,注意是基础

维护并查集

LCT可以当作一个可以删边的并查集,也就是维护一棵树的连通性,比较好写,甚至不用makeroot

洛谷 P2147 [SDOI2008]洞穴勘测

直接维护就可以了,保证:“删掉的边存在;任意时刻任意两个洞穴之间至多只有一条路径。”减少了很多难度。

题目链接 题解

洛谷 P3950 部落冲突

和上面那题一样,只是存边不太好存。

题目链接 代码

维护生成树

一般要查询路径上最大值或最小值的题目需要维护生成树这个贪心来解决。

洛谷 P4172 [WC2006]水管局长

倒序处理所有操作,构造生成树并维护生成树即可。

这里要注意的是边有边权,详细处理方法写在题解里了。

当要连接\((u,v,w)\)时,先split(u,v),查询这条链上有没有比\(w\)更大的边,如果没有就不连,如果有,删掉最大的边再连接。

题目链接 题解

洛谷 P2387 [NOI2014]魔法森林

需要想到正确的枚举方法。

因为这个题还是和链上最大值有关,当有两个关键字时,可以考虑把其中一个关键字先排序,然后按这个顺序枚举边,维护生成树。

比如说以\(a\)为关键字排序,就可以找到在\(a_{i\max}\)为任意存在值时,生成树\(b\)的最小值。

todo:

  • 写一篇题解

题目链接 代码

洛谷 P4234 最小差值生成树

生成树题做多了就能一眼看出来了。但是不知道是lct的话还得想想。

题目链接 代码

QTREE 系列

QTREE

这个鬼题在luogu上只能用C语言交。以前写的树剖懒得改成C语言了,但是lct没用什么stl就很好改了。

C语言注意事项

我是学了一波C语言吧

  1. 头文件<c*>要变成<*.h>。例如<cstdio>-><stdio.h>,剩下的不是c开头的基本不能用,因为都是C++里面才出现的。
  2. C语言中没有bool类型……直接用int代替算了。
  3. 我的码风比较偏C就没有特别多需要改的了……

题目链接 代码

QTREE1

是luogu版本的,没有多组数据。lct裸题。

题目链接 代码

QTREE2

主要是求链上第\(k\)个点。分离出来链后,一定满足点-边-点-……-点-边-点这种结构。我们要查找第\(k\)大元素,就要访问split(u,v)后splay中第\(2k-1\)大的元素。

注意访问(dfs)的时候要pushdown,不然左右关键字大小会错。

todo:

题目链接 代码

维护双连通分量

bzoj 4998 星球联盟

学了一下lct维护双连通分量,用了一堆并查集,样例调了快一个小时。样例过了居然1A了……运气还不错吧。以后还要找题练习。

代码也有待改进。

todo

  • 写一篇题解

题目链接 代码

其他

洛谷 P3203 [HNOI2010]弹飞绵羊

不用换根的lct,感觉是个阉割版,一开始还没敢写。

题目链接 代码

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 【LCT练习记录】 […]

/* */