蒟蒻Andysun06的学习笔记
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ本文章未经博主许可,不能转载!
本文章同步发表于:
一、前言:
ㅤㅤ本文章是蒟蒻我独立创作的,大部分内容都是基础,还包括一些其他东西的用法(例如随机数),本文章
所涉及的知识大部分都是自学的(因为还没找到适合我的老师)。还有一部分,是@FCBM71 和@jijidawang 等大
佬教我的,我在此感谢他们对我的教导,希望我可以和他们共同努力,变得更厉害,也谢谢广大谷友对我的帮
助和支持,我会继续努力的!
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ——By Andysun06
二、目录:
① 栈
- STL——栈的分析及用法
- 手写——栈的分析及用法(速度较快)
② 队列
- STL——队列的分析及用法
- 手写——队列的分析及用法(速度较快)
③ 快速幂
- 3.1 算法分析
- 3.2 模板
④ 线性筛
- 4.1 算法分析
- 4.2 模板
⑤ 并查集
- 5.1 算法分析
- 5.2 模板
⑥ C++随机数
⑦ 前缀和
- 7.1 一维前嘴和
- 7.2 二维前缀和
三、算法笔记
ㅤㅤㅤ ① 栈:
ㅤㅤㅤㅤㅤㅤ- STL——栈的分析及用法:
ㅤㅤㅤㅤㅤㅤㅤ 1. 包含栈的头文件:#include<stack>
。
ㅤㅤㅤㅤㅤㅤㅤ 2. 栈的特点:先进后出,与队列相反
ㅤㅤㅤㅤㅤㅤㅤ 3. 定义一个栈:stack<Type> s;
其中Type
为数据类型。
ㅤㅤㅤㅤㅤㅤㅤ 4. 栈的主要操作:
s.push(a);//将a压入栈顶
s.pop();//删除栈顶的元素,但不会返回
s.top();//返回栈顶的元素,但不会删除
s.size();//返回栈中元素的个数
s.empty();//检查栈是否为空,如果为空返回true,否则返回false
ㅤㅤㅤㅤㅤㅤㅤ 5. 栈的模板题练习:CF26B
ㅤㅤㅤㅤㅤㅤ- 手写——栈的分析及用法:
ㅤㅤㅤㅤㅤㅤㅤ 1. 难度不大,但比STL要更快。
ㅤㅤㅤㅤㅤㅤㅤ 2. 手写模板(具体作用见上面解释):
int q[10000005],top=1;
入栈:q[top++]=n;
出栈:n=q[--top];
查栈顶:n=q[top];
ㅤㅤㅤㅤㅤㅤㅤ 3. 原理:用数组模拟栈的操作。
ㅤㅤㅤ ② 队列:
ㅤㅤㅤㅤㅤㅤ- STL——队列的分析及用法:
ㅤㅤㅤㅤㅤㅤㅤ 1. 包含队列的头文件:#include<queue>
。
ㅤㅤㅤㅤㅤㅤㅤ 2. 队列的特点:先进先出,与栈相反
ㅤㅤㅤㅤㅤㅤㅤ 3. 定义一个队列:queue<Type> q;
其中Type
为数据类型。
ㅤㅤㅤㅤㅤㅤㅤ 4. 队列的主要操作:
q.push(a)//将a压入队列尾部
q.pop()//删除队首元素,但不返回
q.front()//返回队首元素,但不删除
q.back()//返回队尾元素,但不删除
q.size()//返回队列中元素的个数
q.empty()//检查队列是否为空,如果为空返回true,否则返回false
ㅤㅤㅤㅤㅤㅤㅤ 5. 队列的模板题练习:CF637B
ㅤㅤㅤㅤㅤㅤ- 手写——队列的分析及用法:
ㅤㅤㅤㅤㅤㅤㅤ 1. 难度不大,但比STL要更快。
ㅤㅤㅤㅤㅤㅤㅤ 2. 手写模板(具体作用见上面解释):
int q[10000005],l=0,r=1;
入队:q[r++]=n;
出队首:q[++l];
查队首:n=q[l];
原理:用数组模拟队列的操作。
ㅤㅤㅤ ③ 快速幂:
ㅤㅤㅤㅤㅤㅤ- 算法分析:
ㅤㅤㅤㅤㅤㅤㅤ 1. 快速幂用途:用于直接求一个数的 n 次幂会爆数据的题
ㅤㅤㅤㅤㅤㅤㅤ 2. 快速幂原理:具体见这里
ㅤㅤㅤㅤㅤㅤ- 程序模板:
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
ㅤㅤㅤ ④ 线性筛:
ㅤㅤㅤㅤㅤㅤ- 算法分析:
ㅤㅤㅤㅤㅤㅤㅤ 1. 线性筛用途:快速的求范围 n 内的所有素数,其时间复杂度小于暴力求素数。
ㅤㅤㅤㅤㅤㅤㅤ 2. 线性筛原理:具体见这里
ㅤㅤㅤㅤㅤㅤ- 程序模板:
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
ㅤㅤㅤ ⑤ 并查集:
ㅤㅤㅤㅤㅤㅤ- 算法分析:
ㅤㅤㅤㅤㅤㅤㅤ 1.并查集,顾名思义,就是有合并,查找等操作的集合。
ㅤㅤㅤㅤㅤㅤㅤ 2. 文档教程这里
ㅤㅤㅤㅤㅤㅤㅤ 3. 视频教程这里
ㅤㅤㅤㅤㅤㅤ- 程序模板:
#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的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.程序示范:
#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 之间的随机数
ㅤㅤㅤ ⑦ 前缀和:
- 首先介绍:前缀和是什么? 答:个人认为其实就是一种预处理,可以大大降低时
间复杂度,是一种非常方便快捷的基础算法。
- 个人认为一维前缀和思维难度,代码难度较低,几乎是一看就懂的感觉,二维组
要稍加思考,也比较容易。
四、友情链接
五、尾声
ㅤㅤ本文章已经接近尾声了,我很庆幸,你可以坚持看下来,这些东西都是我精心准备的,希望可以对你有帮
助。当然,如果你觉得这篇文章写得好,可以在下面评论,或者点赞。如果你觉得有错误,或者有建议,欢迎
私信我,或者加我的QQ:944898918 。最后,希望你可以继续努力,学习编程,加油!
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ——By Andysun06
六、有关本文章
- 作者:@Andysun06
- 写作开始时间:2020/3/26
- 最近一次更新:2020/4/10
- 版本:V1.5
- 目前更新状况:未完待续……
- 其他:评论请统一为“Orz”
即将推出:
- 图论——基础存图
敬请期待