贪心算法
-
解决问题:最优化问题;
-
优点:是解决最优化问题的最优策略,时间复杂度低;
-
缺点:要满足局部最优解可以推出全局最优解,这意味着在考场上想出一个贪心策略需要通过举例以及证明。
-
常见思考方式:
-
如果是决定谁先做谁后做的,类比排队问题,邻项交换;如果先后有限制关系,比如谁先做谁后做,那么通常套路还是找出最优的,尽可能合并,或者直接将限制的直接干掉。
-
对于树上问题,通常考虑从下到上进行合并。
-
区间问题,首先将区间左/右端点进行排序,然后考虑怎么处理。
-
更为一般的问题,如果几种策略的贡献相等,就考虑对于后面的影响。
-
对于每个必选的,直接考虑每个点如何加入。
-
实在不会,考虑反悔贪心。
-
搜索
深搜优化
-
剪枝
-
可行性剪枝;
-
最优性剪枝;
-
优化搜索顺序;
-
减少冗余状态;
-
-
迭代加深搜索
-
适用范围:不知道明确的搜索边界,或者做搜索树的简单优化;
-
可以达到广搜第一次搜到就是最优解的效果;
-
-
\(IDA^*\) 算法
-
注意:估价函数 \(f()\) 一定要 \(\le\) 真实值,约接近效率越高。
-
适用范围:比较容易得出估价函数的题目。
-
广度优先搜索
-
\(bfs\)
-
适用范围:边权相等,最优化问题,第一次搜到就是最优;
-
优点:在时间常数上,广搜最优,所以对于信息容易放进队列的题目,宜用广搜;
-
缺点:由于必须将信息存进队列,因此若信息过大,则无法放进队列,这时只能深搜。
-
二分
-
适用范围:具有单调性的最优性问题,求最大值最小/最小值最大,排名,变化后的数字。
-
注意:
-
合理选取二分写法,否则造成死循环;
-
如果 \(l,r\) 特别大,考虑加在一起会不会爆 \(int\)。
-
-
优点:可以将最优性问题转化为可行性问题,然后利用条件进行一系列简化。
-
思考方向:
-
利用二分出来的值进行分段 ;
-
利用 \(mid\) 将已知条件进行重新赋值,比如赋值 \(0,1,-1\) 这种较具代表性的数。
-
线性表
栈
-
概念:先进后出的数据结构;
-
适用范围:
-
表达式求值。
- 两个栈,一个数字栈,一个符号栈,遇到数字就往数字栈里面塞,遇到符号,如果这个符号比栈顶符号的优先级大,直接将数字栈弹出了两个算出结果再塞回去,这个符号就不放回去了。否则将符号塞进去,若是遇到左括号,直接塞,遇到右括号,将数字栈和符号栈轮流弹出,直到遇到左括号为止。在将结果塞回去。
-
括号匹配
- 左括号就塞进栈,右括号就将顶上的括号弹出,然后标记那两对是匹配的,一般还会结合 \(dp\) 进行出题,这时需要利用匹配结果进行转移。
-
并查集
-
适用范围:
-
维护图的连通性;
-
维护某种关系;
- 如果是关系较多,考虑扩展域并查集。
-
实现快速找到第一个没有填数字的位置。
- 对于某类区间操作的题目,考虑时间倒流加并查集操作。
-
前缀和与差分
倍增
-
适用范围:
- 对于一步一步跳并统计贡献的暴力,尝试用倍增对其优化。
图论
拓扑排序
- 适用范围:在 \(DAG\) 上 \(dp\) 或者计算;
欧拉路径
-
使用范围:图论建模后,不重复且全部走完边的方案。
-
概念:从一个点出发,不重复地走边,将所有边走完,最后回到一个点;
-
有向图:
-
欧拉路径:要么全部节点入度等于出度,要么有一个节点出度等于入度 \(+1\)(起点),一个节点的入度等于出度 \(+1\)(终点),其他节点的入读等于出度。
-
欧拉回路:全部节点入度等于出度。
-
注意:当前弧优化。
-
-
无向图:
-
类似有向图,此处只需考虑节点度数的奇偶性即可。
-
注意:无向图只能写邻接表存图,否则要用
map
对边进行标记,效率很低。
-
-
思考方向
-
这种题通常会有不能重复,且首尾有些关系的条件,这时要将关键信息放在边,其他信息放在点。
-
可以利用欧拉路径将若干简单环构成的图,进行分解,得到这些环。
-
最短路
最小生成树
-
概念:在图中边权和最小的一棵树。
-
适用范围:
-
找出一颗最小生成树,只是贡献的计算有点奇怪;
-
希望边权尽可能的大/小,可以在图上找一棵最小/大生成树;
-
利用 \(kruskal\) 的性质出题,只需掌握合并的规律即可。
-
联通性问题
-
强连通分量
-
适用范围:有向图。
-
常见功能:
-
将一个有向图转化成一个 \(DAG\);
-
能缩点的题目,通常对于环的处理都很简单,唯一困难就是在 \(DAG\) 的递推上。
-
-
易错点
-
要记得写
is_stack
数组,在满足dfn[x]!=0
时,先判断is_stack[x]
再更新low[nd]
; -
如果不是先
tarjan
的,要用dfn[x]
更新low[nd]
。
-
-
-
边双连通分量
-
适用范围:无向图。
-
常用功能:
-
将一个无向图转化为一棵树;
-
缩边的题目通常上在题目描述上会特别描述,因为变成树以后,所有边都是桥,也就是必须经过的边。
-
-
树论
树的直径
-
概念:树上一条最长链。
-
求解:
-
两边
dfs
可以求出树的直径。 -
若要求出树的直径上的点,设置上一个节点然后往回跳即可。
-
-
性质
-
与一个点距离最远的点,一定是树的直径端点;
-
若树边权为正,则所有树的直径必定有点重合,即没有不相交的两个树的直径。
-
树的重心
-
概念:使得以该点为根的最大子树最小的点。
-
性质:
-
树中所有点到重心的距离和是最小的。
-
重心的最大子树大小不超过整棵树大小一半。
-
最近公共祖先
-
求法:倍增,树剖。
-
基本上树上问题统计贡献或是判定问题都可以在 \(LCA\) 处解决。
树链剖分
-
概念:根据轻重儿子将树剖分成一条条轻重链。
-
维护各种树上信息。
字符串
border
-
概念:最长相等前后缀。
-
性质:
-
字符串 \(s\) 的 \(border\) 的 \(border\) 还是自己的 \(border\)。
-
在原来字符串后添加一个字符,字符串的 \(border\) 长度至多加 \(1\).
-
周期:除去 \(border\) 剩下的就是周期。
-
-
常考题目
-
利用 \(border\) 性质进行出题,一般涉及周期,相同字母覆盖,以及一些失配树的相关问题。
-
利用 \(border\) 的性质实现 \(dp\) 转移。
-
kmp
- 性质:利用 \(border\) 计算出失配数组,便可以在 \(\rm O(n)\) 时间内完成匹配。
哈希
-
使用范围:要对子串进行一定程度的匹配,如果单纯是对整个字符串进行匹配,直接
map
即可。 -
注意:在考场上为了保险,最好写双哈希
字典树
-
适用范围:
-
字符串字典树:进行前缀信息匹配,以及相关计算;
-
01字典树:进行 \(xor\) 相关计算,具有求出排名为第 \(k\) 大的异或值。
-
-
常见技巧:
- 在字典树上标记通常有两种,一种是直接在最后标记,这样计算完全匹配;一种是在过程中的节点标记,这样可以计算匹配前缀。
-
注意:字典树的空间小号算是比较大的,清空时记得清空 \(tot\)。