2018年8月24日训练笔记

并查集&＃xff1a;

并查集中注意事项&＃xff1a;Fa数组初始化为-1&＃xff08;一般初始化为-1&＃xff09;与初始化为i的区别。fa[i]&＃61;&＃61;fa[j]与findset[i]&＃61;&＃61;findset[j]的区别。

并查集求连通分量个数&＃xff1a;HDU 1213 How Many Tables

https://blog.csdn.net/u013480600/article/details/20836111

判断是不是树&＃xff1a;HDU 1325 POJ 1308 Is It A Tree?

https://blog.csdn.net/u013480600/article/details/20968199

离线并查集&＃xff1a;HDU 4496 D-CITY
https://blog.csdn.net/u013480600/article/details/18278857

二维并查集&＃xff1a;HDU 1198 Farm Irrigation

https://blog.csdn.net/u013480600/article/details/20799843

并查集应用&＃xff1a;求连通分量&＃xff0c;判断是不是树。

RMQ&＃xff1a;RMQ问题可以解决对于一个整数数组(当然也可以是其他可比较大小的元素类型)的任意区间[L, R]查询最值时&＃xff0c;以O(1)时间复杂度回答询问。

KMP&＃xff1a;KMP算法求模式串与主串匹配的问题&＃xff0c;KMP算法很重要就是next数组&＃xff08;之前花了大半天看个差不多&＃xff09;&＃xff0c;next[i]表示模式串中前i-1个字符的公共前缀与后缀的长度。Next数组可以用来求字符串的循环节。

线段树与树状数组&＃xff1a;区间更新&＃xff0c;区间查询问题。

字典树&＃xff1a;字典树是一种特殊的搜索树&＃xff0c;可以用来统计字符串数量&＃xff0c;统计前缀词频。