学习笔记
「野__心__家」
·
·
个人记录
蒟蒻Andysun06的学习笔记
#### 本文章同步发表于：
- [洛谷博客](https://www.luogu.com.cn/blog/andysun123/Learning-notes)
- [CSDN博客](https://blog.csdn.net/a_n_d_y_s_u_n__/article/details/105159775)
- [作业部落博客](https://www.zybuluo.com/Andysun06/note/1687658)
- [大号的洛谷博客](https://www.luogu.com.cn/blog/andysun123/Learning-notes)
-------
### 一、前言：
$\ \ \ \ \ \ \ $本文章是蒟蒻我独立创作的，大部分内容都是基础，还包括一些其他东西的用法（例如随机数），本文章所涉及的知识大部分都是自学的（因为还没找到适合我的老师）。还有一部分，是@[FCBM71](https://www.luogu.com.cn/user/45176) 和@[jijidawang](https://www.luogu.com.cn/user/227514) 等大佬教我的，我在此感谢他们对我的教导，希望我可以和他们共同努力，变得更厉害，也谢谢广大谷友对我的帮助和支持，我会继续努力的！
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $——By Andysun06
---------------------------
### 二、目录：
- ① 栈
- STL——栈的分析及用法
- 手写——栈的分析及用法（速度较快）
- ② 队列
- STL——队列的分析及用法
- 手写——队列的分析及用法（速度较快）
- ③ 快速幂
- 3.1 算法分析
- 3.2 模板
- ④ 线性筛
- 4.1 算法分析
- 4.2 模板
- ⑤ 并查集
- 5.1 算法分析
- 5.2 模板
- ⑥ C++随机数
- ⑦ 前缀和
- 7.1 一维前嘴和
- 7.2 二维前缀和
------
### 三、算法笔记
#### $\ \ \ \ \ $ ① 栈：
$\ \ \ \ \ \ \ \ \ \bullet$ STL——栈的分析及用法：
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 1. 包含栈的头文件：`#include<stack>` 。
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 2. 栈的特点：**先进后出**，与队列相反
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 3. 定义一个栈：` stack<Type> s;` 其中`Type`为数据类型。
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 4. 栈的主要操作：
```cpp
s.push(a);//将a压入栈顶
s.pop();//删除栈顶的元素，但不会返回
s.top();//返回栈顶的元素，但不会删除
s.size();//返回栈中元素的个数
s.empty();//检查栈是否为空，如果为空返回true，否则返回false
```
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 5. 栈的模板题练习：[CF26B](https://www.luogu.com.cn/problem/CF26B)
$\ \ \ \ \ \ \ \ \ \bullet$ 手写——栈的分析及用法：
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 1. 难度不大，但比STL要更快。
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 2. 手写模板（具体作用见上面解释）：
```cpp
int q[10000005],top=1;
入栈：q[top++]=n;
出栈：n=q[--top];
查栈顶：n=q[top];
```
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 3. 原理：用数组模拟栈的操作。
------
#### $\ \ \ \ \ $ ② 队列：
$\ \ \ \ \ \ \ \ \ \bullet$ STL——队列的分析及用法：
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 1. 包含队列的头文件：`#include<queue>` 。
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 2. 队列的特点：**先进先出**，与栈相反
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 3. 定义一个队列：` queue<Type> q;` 其中`Type`为数据类型。
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 4. 队列的主要操作：
```cpp
q.push(a)//将a压入队列尾部
q.pop()//删除队首元素，但不返回
q.front()//返回队首元素，但不删除
q.back()//返回队尾元素，但不删除
q.size()//返回队列中元素的个数
q.empty()//检查队列是否为空，如果为空返回true，否则返回false
```
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 5. 队列的模板题练习：[CF637B](https://www.luogu.com.cn/problem/CF637B)
$\ \ \ \ \ \ \ \ \ \bullet$ 手写——队列的分析及用法：
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 1. 难度不大，但比STL要更快。
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 2. 手写模板（具体作用见上面解释）：
```cpp
int q[10000005],l=0,r=1;
入队：q[r++]=n;
出队首：q[++l];
查队首：n=q[l];
```
原理：用数组模拟队列的操作。
-----------
#### $\ \ \ \ \ $ ③ 快速幂：
$\ \ \ \ \ \ \ \ \ \bullet$ 算法分析：
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 1. 快速幂用途：用于直接求一个数的 $n$ 次幂会爆数据的题
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 2. 快速幂原理：具体见[这里](https://blog.csdn.net/henu111/article/details/81188659?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522158523255919726867821069%2522%252C%2522scm%2522%253A%252220140713.130056874..%2522%257D&request_id=158523255919726867821069&biz_id=0&utm_source=distribute.pc_search_result.none-task)
$\ \ \ \ \ \ \ \ \ \bullet$ 程序模板：
```cpp
int pow(int a, int b) {
int ans=1,base=a;
while(b!=0) {
if(b&1)//判断b的奇偶
ans*=base;//当n为奇数时，乘以base（当前权值下的a）
base*=base;
b>>=1;//等价于b/=2
}
return ans;
}
```
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 1. 快速幂的模板题练习：[P1226](https://www.luogu.com.cn/problem/P1226)
-------------------------
#### $\ \ \ \ \ $ ④ 线性筛：
$\ \ \ \ \ \ \ \ \ \bullet$ 算法分析：
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 1. 线性筛用途：快速的求范围 $n$ 内的所有素数，其时间复杂度小于暴力求素数。
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 2. 线性筛原理：具体见[这里](https://zhuanlan.zhihu.com/p/108674990)
$\ \ \ \ \ \ \ \ \ \bullet$ 程序模板：
```cpp
bool isPrime[100000010];
int Prime[5000010], cnt=0;
void GetPrime(int n) {
memset(isPrime, 1, sizeof(isPrime));
isPrime[1] = 0;
for(int i = 2; i <= n; i++) {
if(isPrime[i])
Prime[++cnt] = i;
for(int j=1;j<=cnt&&i*Prime[j]<=n; j++) {
isPrime[i*Prime[j]] = 0;
if(i % Prime[j] == 0)
break;
}
}
}
//main函数第一行加上 GetPrime(n) n为范围
```
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 1. 线性筛的模板题练习：[P3383](https://www.luogu.com.cn/problem/P3383)
----------------------
#### $\ \ \ \ \ $ ⑤ 并查集：
$\ \ \ \ \ \ \ \ \ \bullet$ 算法分析：
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 1.并查集，顾名思义，就是有合并，查找等操作的集合。
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 2. 文档教程[这里](https://blog.csdn.net/low5252/article/details/90611503)
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 3. 视频教程[这里](https://www.bilibili.com/video/av26268911)
$\ \ \ \ \ \ \ \ \ \bullet$ 程序模板：
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
int a[10001],i;
int zhao(int x) { //用来查找x的祖宗
if(a[x]==x) { return x; }
return a[x]=zhao(a[x]);
}
bool cha(int x,int y) { //用来判断x,y的祖宗是不是同一个人
if(zhao(x)==zhao(y)) { return true;
} else { return false; }
}
void bin(int x,int y) { //用来合并x,y
if(cha(x,y)==false) a[zhao(x)]=zhao(y);
}
int main() {
int N,M;
scanf("%d%d",&N,&M);
for(i=1; i<=N; ++i) a[i]=i;
for(i=1; i<=M; ++i) {
int z,x,y;
scanf("%d%d%d",&z,&x,&y);
if(z==1) {
bin(x,y);
} else {
if(cha(x,y))
printf("Y\n");
else
printf("N\n");
}
}
return 0;
}
```
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 1. 本程序为并查集模板[P3367](https://www.luogu.com.cn/problem/P3367)的AC程序
---------------------
#### $\ \ \ \ \ $ ⑥ C++随机数：
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 1. 随机数头文件 `#include <cstdlib>` 和 `#include<ctime>`
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 2. 使用宏定义 `#define random(a,b) (rand()%(b-a)+a)`
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 3. 在开头加上 `srand((int)time(0));`
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 4. 最后，在程序中加入 `random(l,r);` 就可以求 $l$ 到 $r$ 之间的随机数了。
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 5.程序示范：
```cpp
#include <iostream>
#include <cstdlib>
#include <ctime>
#define random(a,b) (rand()%(b-a)+a)
using namespace std;
int main(){
srand((int)time(0)); // 产生随机种子,把0换成NULL也行
for (int i = 0; i < 10; i++){
cout<<random(5, 10)<<" ";
}
return 0;
}
//此程序可以产生 5 到 10 之间的随机数
```
-----------------------
#### $\ \ \ \ \ $ ⑦ 前缀和：
$\ \ \ \ \ \ \ \ \ \bullet$ 首先介绍：前缀和是什么？ 答：个人认为其实就是一种预处理，可以大大降低时间复杂度，是一种非常方便快捷的基础算法。
$\ \ \ \ \ \ \ \ \ \bullet$ 一维前缀和：
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 1.具体文章讲解[这里](https://blog.csdn.net/XT_NOI/article/details/72666275)
$\ \ \ \ \ \ \ \ \ \bullet$ 二维前缀和：
$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 1.具体文章讲解[这里](https://blog.csdn.net/XT_NOI/article/details/72715904)
$\ \ \ \ \ \ \ \ \ \bullet$ 个人认为一维前缀和思维难度，代码难度较低，几乎是一看就懂的感觉，二维组要稍加思考，也比较容易。
------------------
### 四、友情链接
- [作者个人主页](\user\70299)
- [作者其他文章](https://www.luogu.com.cn/blog/andysun123/)
- [XSLM 官方团队](https://www.luogu.com.cn/team/25191)
- [猫国建设者 讨论群](https://www.luogu.com.cn/team/23467)
- [钺Programmer 的个人主页](www.luogu.com.cn/user/153141)
### 五、尾声
$\ \ \ \ \ \ \ $本文章已经接近尾声了，我很庆幸，你可以坚持看下来，这些东西都是我精心准备的，希望可以对你有帮助。当然，如果你觉得这篇文章写得好，可以在下面评论，或者点赞。如果你觉得有错误，或者有建议，欢迎私信我，或者加我的QQ：944898918 。最后，希望你可以继续努力，学习编程，加油！
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $——By Andysun06
### 六、有关本文章
- 作者：@[Andysun06](\user\70299)
- 写作开始时间：2020/3/26
- 最近一次更新：2020/4/10
- 版本：V1.5
- 目前更新状况：未完待续……
- 其他：评论请统一为“Orz”
- 字数：约为 4030
------------------------------
即将推出：
- 图论——基础存图
敬请期待