算法知识点

树、图的存储：链式前向星

	Edge{u,v,next,weight}和head[]辅助数组。
	head[]存Edge的序号，为以对应顶点为起点的边。
	Edge中，u:起点，v:终点，next：以u为起点的下一条边的序号，无边返回为-1

	初始化：
	edge[i].next=head[u]
	head[u]=i

	遍历：
	for(int i = head[n];i!=-1;i=edge[i].next){
	//操作edge[i].v
	}
	注：无向图edge要开2倍的大小

//图的其他数据结构：邻接矩阵(二维数组)、邻接表(Vector<Vector>)

图的遍历：
DFS:递归实现，递归完要回退
BFS:队列优化
单源点最短路径：SPFA算法(队列优化，不断松弛操作)，可有负边不能负环。
或Dijkstra算法，不能负边or负环。一次将单源点到所有点的最小距离都生成了，
不断选最小点，更新未选点。
图的最小生成树
prim算法：边较少。(不断从所有已选点中选距离最短的相邻未选点)
Kruskal算法：边较多。（所有边中不断找最小边，判断是否在一个连通分量中）
判断连通分量用到路径优化后的并查集，注意更新parent[]数组一定要更新根节点。
关于已选集合和未选集合的实现：可用visited数组来存储状态。
在一些树形动态规划问题中，可能会子结点对应多个父结点，所以开Edge数组要开2倍的大小，而且在前向星便利时要除去父结点的情况。
动态规划要点
1.列状态转移方程，常分选择/不选择当前结点两种情况(用二维数组a[n][2]表示)
2.一定要将每种情况的值存储下来，这样才能保证效率。用二维数组存↑
3.程序上常常用递归或for循环实现
归并排序：
【递归】的思想对数组进行排序，包括排序和合并两个步骤。
先将数组分为左右两部分，分别排序，再将有序的两部分合并。
可用一个辅助数组temp来临时保存数据来实现原数组排序。
可用归并排序来求逆序数：
一个数组的逆序数【左半部分逆序数】+【右半部分逆序数】+【左半部分比右半部分大的数的个数（在合并左、右时计算）】
二叉树的操作中注意可能会出现单根的情况，会导致树深度大大增加。
此时考虑用二叉平衡树。
平衡二叉树的简化版->splay树，伸展树。

一些技巧

若对循环设置一个判断的变量，要注意在每次循环前/后是否需要对变量置为初始值。防止上一次的判断结果影响这一次的判断。
eg：<完美的代价>中n为奇数条件pos的使用。
日期的计算：
计算从日期a到日期b的天数n
最常见如果a算在内但不算b那就是n=b-a。
eg:算天数差/经过了多少天/隔多少天
如果a和b这两天也算在内就是n=b-a+1
如果不算a和b这两天就是n=b-a-1
for()循环，满足一定条件才执行段内语句，要在段内用if语句，不能将条件写到for()内，否则会变成中止条件，而不是continue条件。
一些实际的应用题，可用模拟的方法来求解。确定一个最小的变化单元，不断模拟。
eg：<龟兔赛跑>问题中时间一次+1s模拟
对于结束情形的判断，若判断各种结束情况很复杂且题目涉及总数量，可改为直接检测数量，会简化许多
在递归中，若表达式涉及传入递归函数的参数，要先写回传入的变量，再写递归式。防止下一次递归中改变了变量的值。
在进行按位操作时，输入、输出顺序和运算顺序是相反的。
但输入输出可都用相反顺序(即正常读入读出顺序)，最后反反得正，结果不受影响。
关于输出空格/空行的控制，for循环下可对循环次数进行检测(首次/末次不输出)，while循环下可设标志位检测。
大while中套小while，小while每次的判断条件也要保证大while的条件，保证小while的循环不会使大while“循环越界”。

Post Date： 2018-01-20