佳木斯集训知识要点

Day1：图论，字符串

1. 连通性使用并查集最快捷方便（尽管还有其他数据结构）
2. 简单图联通问题有时可以用最短路来做
3. 复杂图论可以转化成Tarjan，拓扑排序做，有向图考虑是否可以缩点，无向图可以考虑是否有割点割桥。
4. 如果边有边权，可以考虑排序或其他操作让题中条件统一考虑
5. 关于字符串问题
6. 字符串匹配可以哈希和kmp，哈希的话好理解，其实双哈希通常可以解决所有问题，但是kmp可以演化成AC自动机，解决更多字符串问题。
7. 后缀数组和后缀自动机没有听懂。。。。。。

Day2：后缀自动机，树上问题，倍增差分树链剖分

1. 后缀自动机没听懂
2. 差分有点像前缀和或者是线段树懒标记，比较好懂，但我只能解决极其简单问题（模板）
3. 倍增和树链剖分学长好像没讲

Day3：数论，莫比乌斯反演

1. 关于莫比乌斯反演证明几乎没有听懂，经过例题好像知道他们是解决大多数求gcd问题的
2. 好像又讲了FWT，没有听懂
3. 不过关于大因数分解倒是还可以

Day4：容斥原理

1. 学长给的公式仅仅是看懂一点。
2. 凑系数根本没听懂

Day5：树上问题LCA

1. 关于lca的链剖和tarjan做法比较了解，关于RQM和倍增比较生疏。
2. 关于虚树只知道它的用途和原理，但做题时发现不了什么时候用它。
3. 好像没有别的了

Day6：二分答案

1. 感觉区间待修改查询还是主席树比较好懂一些。。。。。。。
2. 有些题不知道是否有单调性，不知道可以用二分答案。

Day7：状压和树形dp

1. 状压感觉还可以，能做出小部分题（一道或两道）
2. 插头dp不会
3. 树形dp之前没接触过，十分费劲。

Day8：期望dp

没听懂

Day9：热点问题

1. 只有前两题听懂了思路
2. 其他题没听懂。

总结：

1. 学长多次提到网络流，我应该学一下
2. 集训给我点明了学习的方向