算法零碎知识点 01

二分

较为简单的方法，直接套模板就可以

贪心

常与二分结合使用，进行相关的求解

链式前向星

链式前向星：用数组来存储树 （->另外一个好的思路是使用孩子兄弟链表表示法）

int head[N];
typedef struct Edge
{
 int to,next;
 long long w;
}Edge;
Edge e[M];
// 变量声明模板</pre>

kruskal

借助并查集来实现，时间复杂度较低，速度较快，为求解最小生成树问题的优选之法。

typedef struct Kedge
{
 int from,to,w;
 bool operator<(const Kedge &x) const
 {
 return w<x.w;  // 升序
 }
}Kedge;
Kedge ke[M];
int sum,t;
​
int f(int x)
{
 if(x==fa[x])
 return x;
 return fa[x]=f(fa[x]);
}
void kruskal()
{
 // 每个人都是自身的代表
 for(int i=1;i<=n;i++)
 fa[i]=i;
 sort(ke+1,ke+m+1);
 for(int i=1;i<=m;i++)
 {
 int faf=f(ke[i].from),fat=f(ke[i].to);
 if(faf==fat)
 continue;
 t++;
 f[fat]=faf;
 sum+=ke[i].w;
 if(t==n-1)
 return;
 }
}

prim

两种实现方法：

1. 二维数组法：

   优点：实现方式较为简单，较为直观 缺点：特殊数据下，会超出空间的限制，占用过多的空间

2. 链式前向星

   优点：占用空间比较少，效率较高 缺点：较为抽象、不直观

dijkstra单源最短路径

1. 二维数组法/邻接矩阵法

   优点：容易理解，比较直观 缺点：占用空间过多

2. 链式前向星

int head[N];
typedef struct
{
 int to,next;
 long long w;
}Edge;
Edge e[M];
long long dis[N];
bool vis[N];
// 变量声明模板

需要注意，先选中起始顶点并访问后，需要先更新，再进行下一次选择。

3. 优先队列

   堆优化，效率极高，对于解决标准的问题最短路径问题非常实用，且代码量较少，为推荐的方法。 此种方法，使用dis[temp.to]<temp.dis 进行判断和vis[temp.cur] 进行判断均可，某些情况下（暂时不知），只有后者才可以正常运行。

注意

dijkstra算法只能算最短的非负路径，即如果有负边权的边，就会出现问题（一般不会出这样的边）

spfa算法可以解决此类问题（堆优化）—使用优先队列。

DP动态规划

1. 对于上楼梯问题，斐波那契数列求解和记忆搜索的区别：

   如果楼梯上界是可以确定的，可以定义特定大小的数组，利用斐波那契数列进行求解，较为简单；

   如果楼梯上界是不确定的，需要用记忆搜索；

2. dp问题(动态规划)，一般是用循环来求解：

   合唱队形

   数楼梯

   过河卒

   装箱子

   以上问题，都是通过循环遍历进行求解；
   至于记忆化搜索，一般涉及到递归；且记忆化搜索的效率显著高于普通搜索

   Function