非广告：csdn的博客

东西太多，luogu列表不太友好(没有有标题链接，不便寻找）

qwq

为SCP初赛选手（我）收集的各种定理qwq

更新：

1、为了初赛都能用，不限于定理了

2、主旨为在短时间内复习各算法，备初赛

3、请确定你学习（学懂了）了 的基础知识。

可能会一直更新下去qwq

最新：2021/9/11 10:03

1、主定理

在求某一分治（递推？）算法时间复杂度中适用。

规模为 的问题通过分治，得到 个规模为 的问题，每次递归带来的额外计算为

即 。

求执行 的时间复杂度。

定理：

若 ，

若 ，

若 ，

套就完事儿了 证明请bdfs

2、等比数列

指一个数列所有数有公共比。

比如：，，，，

此时公比为 。

等比数列通项公式为

即为数列首项， 就是公比。

比如说，求上面那个等比数列的第五个数。

求得 。

根据通项公式，我们可以轻松得到前 项的求和公式。

还是比如：求上面那个数列的前五项之和。

求得 。

至于推导嘛，它来了！

2.1 等比数列求和公式推导

首先，先将通项公式列出来。

提 。

添一个 。

乘开，

消掉一大堆，

此时要求 且

最终得到

应用嘛，其实很广的。

2.2 应用：h层满k叉树求节点个数

第 层 个；

第 层 个；

第 层 个；

第 层 个；

…

第 层 个。

这不就等比数列吗。上求和公式！

注意！ 这里其实有 层，所以为什么是 。

题目链接：Noip2018提高 - 第四题

3、贪心

贪心算法（英语：greedy algorithm），是用计算机来模拟一个 “贪心”的人 做出决策的过程。这个人十分贪婪， 每一步行动总是按某种指标选取最优的操作。 而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。
可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。
——Copy by OI-WIKI

从中可以看出，贪心所讲究的，是思维的 贪度和正确，二者一样重要。 （贪度，即为贪心的层次，越贪心，贪度越高 我瞎掰扯的， 理解就好）

首先，贪度的提高并不是一次思考就能完成的。

就好比时间复杂度需要一步步优化。

贪心的主要内容，证明等皆在OI-Wiki中有讲述，可以到oi-wiki找到详细的讲述。

4、二分

二分，可以理解为分成两半。在二分基础应用中，二分是用来在一 有序 数列中寻找数的快速方法。

注：必须有序！

比如，

我需要在 中寻找第一个比 大于（等于）的数。

比如说 ，则找到的数下标为 。

4.1 基本实现

1、令

2、又令

3、对于 ，

若 ，因为整体有序，所以 一定在 左边（或它本身）。

这里等于号放在这里，是因为即使等于了，第一个说不定还在前面。

若 ，同理， 一定在 右边。

持续进行步骤二和步骤三，当 时，就找到了。

这就是最基本的实现。

实现代码：（arr为有序序列）

1
2
3
4
5
6
7
8
9
10
11
12

int binary_search(int start, int end, int key) {
  int ret = -1;  // 未搜索到数据返回-1下标
  int mid;
  while (start <= end) {
    mid = start + ((end - start) >> 1);  // 直接平均可能会溢出，所以用这个算法
    if (arr[mid] <= key)
      start = mid + 1;
    else if (arr[mid] > key)
      end = mid - 1;
  }
  return ret;  // 单一出口
}

4.2 进阶实现

首先，二分一般实现于最值最化。

简化最值最化的要求：

1、答案在一个固定区间内；

2、查找不容易，判断容易（比如说找数）；

3、可行解对于区间满足一定的单调性。

如果一个数组中的左侧或者右侧都满足某一种条件，而另一侧都不满足这种条件，也可以看作是一种有序（如果把满足条件看做 ，不满足看做 ，至少对于这个条件的这一维度是有序的）

这就是指某一个数组的左边 或 右边都满足某一条件，即单调性

可以理解为上上上上面的例子中， V[3] 左边都满足小于 3 这个条件。

4.3 实际应用

见二分答案

5、三分（待填坑）

6、哈希

对于初赛来说，只需理解哈希函数以及哈希碰撞即可。

哈希列表的概念是差不多的

哈希函数 & 哈希碰撞

简单来说，就是将某一难处理的数值、字符串通过某一处理函数处理成简单的数字。

看例子就可以学懂了：

设哈希函数为：，

则 的哈希值为 ， 的哈希值也为 。

此时 和 的哈希值相同，有同样的哈希值保存，会导致碰撞，称为哈希碰撞

7、KMP（待填坑）

放链接。

8、最小生成树（待填坑）

放链接。

9、最短路

这里只讲 Floyd，Dijkstra，SPFA

提醒： 除了 Floyd 算法以外，都建议使用邻接表。邻接矩阵时间复杂度为O(n^2)，等同于没优化

9.1 Floyd

时间复杂度：

评价：最简单的最短路算法，最高的时间复杂度，最划算的多源最短路。

注意事项：中间节点k一定要放在最外层，至于后果，需按数据手推（

思路：一一枚举每两个点的最短路。

样例代码：

1
2
3
4
5
6
7
8
9
10
11
12

cin>>n>>m;
memset(f,63,sizeof(f));
for(int i=1;i<=m;i++)
{
	cin>>x>>y>>dist;
	f[x][y]=dist;
}
//Floyd
for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

9.2 Dijkstra

时间复杂度：

在稀疏图中，使用二叉堆实现的 Dijkstra 法的 即 较 Bellman-Ford (SPFA) 算法的 具有较大的效率优势；

而在稠密图中，这时候使用暴力做法 较二叉堆实现更优。

但一般只使用优先队列法 ，代码最清晰简短，但时间复杂度在稀疏图上比二叉堆略差。

评价：十分经典的单源最短路，在单源最短路中时间复杂度最强，但不能处理负环。各种方法形成不同的时间复杂度，容易考到。

注意事项：不能处理负环！

思路：推荐这篇博客

样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

struct edge {
	int v, w;
};
struct node {
	int dis, u;
	bool operator>(const node& a) const { return dis > a.dis; }
};
vector<edge> e[maxn]; //方便的邻接表？
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node> > q; 
//优先队列，其实可以直接priority_queue<node> q;
void dijkstra(int n, int s) {
	memset(dis, 63, sizeof(dis));
	dis[s] = 0;
	q.push({0, s});
	while (!q.empty()) {
		int u = q.top().u;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (auto ed : e[u]) { //C++11新语法，建议没见过的bdfs
			int v = ed.v, w = ed.w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				q.push({dis[v], v});
			}
		}
	}
}

对于上面 vector<edge> e[maxn]，是邻接表的一种实现，内存消耗是动态的，并且最方便，但时间复杂度 可能 偏高。

9.3 SPFA

时间复杂度：随机数据中表现优秀，但平均时间复杂度为 。

评价：最好理解的最短路，最容易Cu卡爆的最短路。

注意事项：能处理负环。

思路：有点类似BFS，是BF的队列优化版本。

样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

struct edge {
  int v, w;
};
vector<edge> e[maxn];
int dis[maxn], cnt[maxn], vis[maxn];
queue<int> q;
bool spfa(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0, vis[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop(), vis[u] = 0;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        cnt[v] = cnt[u] + 1;  // 记录最短路经过的边数
        if (cnt[v] >= n) return false;
        // 在不经过负环的情况下，最短路至多经过 n - 1 条边
        // 因此如果经过了多于 n 条边，一定说明经过了负环
        if (!vis[v]) q.push(v), vis[v] = 1;
      }
    }
  }
  return true;
}

-by oi-wiki

10、位运算

这位大佬的博客

写的不好，勿喷