qwq
为SCP初赛选手（我）收集的各种定理qwq
更新：
1、为了初赛都能用，不限于定理了
2、主旨为在短时间内复习各算法，备初赛
3、请确定你学习（学懂了）了 \(\texttt{oi}\) 的基础知识。
可能会一直更新下去qwq
最新：2021/9/11 10:03
@
-
qwq
- 1、主定理
-
2、等比数列
- 2.1 等比数列求和公式推导
- 2.2 应用：h层满k叉树求节点个数
- 3、贪心
-
4、二分
- 4.1 基本实现
- 4.2 进阶实现
- 4.3 实际应用
- 5、三分（待填坑）
- 6、哈希
- 7、KMP（待填坑）
- 8、最小生成树（待填坑）
-
9、最短路
- 9.1 Floyd
- 9.2 Dijkstra
- 9.3 SPFA
- 10、位运算
1、主定理
在求某一分治（递推？）算法时间复杂度中适用。
规模为 \(n\) 的问题通过分治，得到 \(a\) 个规模为 \(\dfrac{n}{b}\) 的问题，每次递归带来的额外计算为 \(O(n^d)\)
即 \(T(n)=aT(\dfrac{n}{b})+O(n^d)\)。
求执行 \(T(n)\) 的时间复杂度。
定理：
若 \(a=b^d\)，\(T(n) = O(n^d \log{n})\)
若 \(a<b^d\)，\(T(n) = O(n^d)\)
若 \(a>b^d\)，\(T(n) = O(n^{\log_ba})\)
套就完事儿了 证明请bdfs
2、等比数列
指一个数列所有数有公共比。
比如：\(1\)，\(2\)，\(4\)，\(8\)，\(...\)
此时公比为 \(2\)。
等比数列通项公式为
\]
\(a_1\) 即为数列首项，\(q\) 就是公比。
比如说，求上面那个等比数列的第五个数。
\(a_5=1\times (2^{5-1})\)
求得 \(a_5=16\)。
根据通项公式，我们可以轻松得到前 \(n\) 项的求和公式。
\]
还是比如：求上面那个数列的前五项之和。
\(S_5=\dfrac{1\times (2^5-1)}{2-1}\)
求得 \(S_5=31=1+2+4+8+16\)。
至于推导嘛，它来了！
2.1 等比数列求和公式推导
首先，先将通项公式列出来。
\]
提 \(a_1\)。
\]
添一个 \((q-1)\)。
\]
乘开，文章来源地址:https://www.yii666.com/article/756390.html
\]
消掉一大堆，
\]
此时要求 \(q\neq 0\) 且 \(q\neq 1\)
最终得到
\]
应用嘛，其实很广的。
2.2 应用：h层满k叉树求节点个数
第 \(0\) 层 \(k^0\) 个；
第 \(1\) 层 \(k^1\) 个；
第 \(2\) 层 \(k^2\) 个；
第 \(3\) 层 \(k^3\) 个；
...
第 \(h\) 层 \(k^h\) 个。
这不就等比数列吗。上求和公式！
\(N=\dfrac{k^{h+1}-1}{k-1}\)
注意！ 这里其实有 \(h+1\) 层，所以为什么是 \(h+1\)。网址:yii666.com
题目链接：Noip2018提高 - 第四题
3、贪心
贪心算法（英语：greedy algorithm），是用计算机来模拟一个 “贪心”的人 做出决策的过程。这个人十分贪婪， 每一步行动总是按某种指标选取最优的操作。 而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。
可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。
——Copy by OI-WIKI
从中可以看出，贪心所讲究的，是思维的 贪度和正确，二者一样重要。 （贪度，即为贪心的层次，越贪心，贪度越高 我瞎掰扯的， 理解就好）
首先，贪度的提高并不是一次思考就能完成的。
就好比时间复杂度需要一步步优化。
贪心的主要内容，证明等皆在OI-Wiki中有讲述，可以到oi-wiki找到详细的讲述。
4、二分
二分，可以理解为分成两半。在二分基础应用中，二分是用来在一 有序 数列中寻找数的快速方法。
注：必须有序！
比如，\(V=\{1,2,3,3,5\}\)
我需要在 \(V\) 中寻找第一个比 \(a\) 大于（等于）的数。
比如说 \(a=3\)，则找到的数下标为 \(3\)。
4.1 基本实现
1、令 \(\texttt{l}=1,\texttt{r}=|V|.\)
2、又令 \(\texttt{mid}=(l+r)/2.\)
3、对于 \(V_{mid}\)，
若 \(V_{mid}\leq a\)，因为整体有序，所以 \(a\) 一定在 \(\texttt{mid}\) 左边（或它本身）。
这里等于号放在这里，是因为即使等于了，第一个说不定还在前面。
若 \(V_{mid}< a\)，同理，\(a\) 一定在 \(\texttt{mid}\) 右边。
持续进行步骤二和步骤三，当 \(l=r\) 时，就找到了。
这就是最基本的实现。
实现代码：（arr为有序序列）
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、哈希
对于初赛来说，只需理解哈希函数以及哈希碰撞即可。
哈希列表的概念是差不多的
哈希函数 & 哈希碰撞
简单来说，就是将某一难处理的数值、字符串通过某一处理函数处理成简单的数字。
看例子就可以学懂了：
设哈希函数为：\(H(x)=\lfloor x/5\rfloor\)，
则 \(1\) 的哈希值为 \(H(1)=0\)，\(2\) 的哈希值也为 \(H(2)=0\)。
此时 \(1\) 和 \(2\) 的哈希值相同，有同样的哈希值保存，会导致碰撞，称为哈希碰撞
7、KMP（待填坑）
放\(\texttt{OI-Wiki}\)链接。
8、最小生成树（待填坑）
放\(\texttt{OI-Wiki}\)链接。
9、最短路
这里只讲 Floyd，Dijkstra，SPFA文章地址https://www.yii666.com/article/756390.html
提醒： 除了 Floyd 算法以外，都建议使用邻接表。邻接矩阵时间复杂度为O(n^2)，等同于没优化
9.1 Floyd
时间复杂度：\(O(n^3)\)
评价：最简单的最短路算法，最高的时间复杂度，最划算的多源最短路。
注意事项：中间节点k一定要放在最外层，至于后果，需按数据手推（
思路：一一枚举每两个点的最短路。
样例代码：
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 法的 \(O((n+m)\log n)\) 即 \(O(m\log n)\) 较 Bellman-Ford (SPFA) 算法的 \(O(nm)\) 具有较大的效率优势；
而在稠密图中，这时候使用暴力做法 \(O(n^2+m)\) 较二叉堆实现更优。
但一般只使用优先队列法 \(O(m\log m)\) ，代码最清晰简短，但时间复杂度在稀疏图上比二叉堆略差。
评价：十分经典的单源最短路，在单源最短路中时间复杂度最强，但不能处理负环。各种方法形成不同的时间复杂度，容易考到。
注意事项：不能处理负环！
思路：推荐这篇博客
样例代码：
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
时间复杂度：随机数据中表现优秀，但平均时间复杂度为 \(O(nm)\)。
评价：最好理解的最短路，最容易Cu卡爆的最短路。
注意事项：能处理负环。
思路：有点类似BFS，是BF的队列优化版本。
样例代码：
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、位运算
这位大佬的博客
写的不好，勿喷