CSP-S初赛基础知识整理-Toy模板网

这篇具有很好参考价值的文章主要介绍了CSP-S初赛基础知识整理。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

CSP-S初赛基础知识整理

RT

持续更新中
关于部分 $l a t e x$ 在 csdn 不能很好的显示，更好的阅读体验。

[1]计算机基础知识

计算机系统的组成

硬件系统和软件系统。

计算机硬件的五大组成

控制器、运算器、存储器、输入设备和输出设备。

[1-2]进制及其转化和运算

[1-2]二进制

[1]基本定义及应用

逢二进一。后缀为 $\texttt{B}$ 。
是计算机主要存储方式。

[1]基本运算

加法 0+0=0，0+1=1，1+1=10。
减法 0-0=0，1-0=1，1-1=0。
乘法 0×0=0，0×1=0，1×0=0，1×1=1。

[2]位运算

and(&)

	0	1
0	0	0
1	0	1

or(|)

	0	1
0	0	1
1	1	1

xor(^)

	0	1
0	0	1
1	1	0

not(~)

0	1
1	0

[1]其他进制及转换

八进制

有 $0\to7$ 8个字符组成，与二进制1换3。
后缀为 $\texttt{O}$ 。

2进制	8进制
000	0
001	1
010	2
011	3
100	4
101	5
110	6
111	7

十六进制

有 $0\to9,A\to F$ 16个字符组成，与二进制1换4。
后缀为 $\texttt{O}$ 。

2进制	8进制
0000	0
0001	1
0010	2
0011	3
0100	4
0101	5
0110	6
0111	7
1000	8
1001	9
1010	A
1011	B
1100	C
1101	D
1110	E
1111	F

十进制

有 $0\to9$ 10个字符组成。
后缀为 $\texttt{D}$ 。

2进制	10进制
0000	0
0001	1
0010	2
0011	3
0100	4
0101	5
0110	6
0111	7
1000	8
1001	9
1010	10
1011	11
1100	12
1101	13
1110	14
1111	15

[1]主要人物及贡献

名字	国籍	信息学主要贡献	称号身份
艾伦·麦席森·图灵	英	图灵机，图灵奖，图灵实验	计算机科学之父，人工智能之父
约翰·冯·诺依曼	美籍匈牙利	体系构想，程序存放于内存	计算机之父、博弈论之父
克劳德·艾尔伍德·香农	美	提出了信息熵的概念	信息论的创始人
姚期智	中	通讯复杂度，伪随机数生成	奠定现代密码学
艾达·拉芙蕾丝	英	Ada语言	第一个程序员，计算机程序创始人

[5]Linux

命令	作用
mkdir	创建目录
cp	复制文件(夹)
rm	删除文件(夹)
mv	重命名/移动
cd	切换工作目录
pwd	打印目录路径
ls	显示目录文件
time	测量运行时间
g++	编译命令
gdb	调试命令
./a	运行 a

time

real time > cpu time = user time + sys time

real time

表示从程序开始到程序执行结束时所消耗的时间，包括CPU的用时。

user time

值表示程序本身，以及它所调用的库中的子例程使用的时间。

sys time

是由程序直接或间接调用的系统调用执行的时间。

gdb

默认

gdb ./a

对 $\texttt{a}$ 进行调试。

gdn --args ./a 1.txt

对 $\texttt{a}$ 进行调试并标记输入文件为 $\texttt{1.txt}$ 。

其他操作

b(reak)

设置断点。

display

查看变量或式的值。

c(ontinue)

开始连续（而非单步）执行。

s(ept)

进入函数调试。

[5]编译选项

默认

g++ 1.cpp -o 1.exe

其中 $\texttt{1.cpp}$ 为源文件， $\texttt{1.exe}$ 为输出文件。

额外编译指令

-x language filename

将 $\texttt{filename}$ 这个文件以 $\texttt{language}$ 的语言编译。

注意：-x 指令对其之后的所有文件都生效。

-x none filename

取消上一个指令的效果。

-c

只将文件生成为 $\texttt{obj}$ (二进制)文件。

-S

只将文件生成为汇编代码。

-o

标记输出文件。

-O0,-O1,-O2,-O3

开启 $\texttt{O0(1,2,3)}$ 优化。

-g

产生调试信息。

[5]STL

STL

[5-8]算法

[6]复杂度分析

空间复杂度分析

时间复杂度分析

主定理

令 $T(n)=a\times T(\frac{n}{b})+f(n)$

当 $a\geq 1\ and\ b > 1$ 时

若 $\exists\epsilon > 0$ ，有 $f(n)=O\left(n^{\log_{\ b}{\ a-\epsilon}}\right)$ ，则 $T(n)=\Theta\left(n^{\log_{\ b}{\ a}}\right)$ 。
若有 $f(n)=O\left(n^{\log_{\ b}{\ a}}\right)$ ，则 $T(n)=\Theta\left(n^{\log_{\ b}{\ a}}\log{n}\right)$ 。
若 $\exists\epsilon > 0$ ，有 $f(n)=O\left(n^{\log_{\ b}{\ a+\epsilon}}\right)$ 且对于常数 $c < 1$ 和所有足够大的 $n$ ，有 $a\times f(\frac{n}{b})\leq c\times f(n)$ ,则 $T(n)=\Theta\left(f(n)\right)$ 。

[6]基础算法

分治算法

[5-6]排序算法

排序算法	平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	排序方式	稳定性	评级
归并排序	$\Theta\left({n\log{n}}\right)$	$\Theta\left({n\log{n}}\right)$	$\Theta\left({n\log{n}}\right)$	$\Theta\left({n}\right)$	非原地排序	稳定	5
快速排序	$\Theta\left({n\log{n}}\right)$	$\Theta\left({n\log{n}}\right)$	$\Theta\left({n^2}\right)$	$\Theta\left({\log{n}}\right)$	原地排序	不稳定	5
基数排序	$\Theta\left({n\times k}\right)$	$\Theta\left({n\times k}\right)$	$\Theta\left({n\times k}\right)$	$\Theta\left({n + k}\right)$	非原地排序	稳定	6
堆排序	$\Theta\left({n\log{n}}\right)$	$\Theta\left({n\log{n}}\right)$	$\Theta\left({n\log{n}}\right)$	$\Theta\left({1}\right)$	原地排序	不稳定	6
桶排序	$\Theta\left({n + k}\right)$	$\Theta\left({n + k}\right)$	$\Theta\left({n^2}\right)$	$\Theta\left({n + k}\right)$	非原地排序	稳定	5
树形选择排序（竞标赛排序）	$\Theta\left({n\log{n}}\right)$	$\Theta\left({n\log{n}}\right)$	$\Theta\left({n\log{n}}\right)$	$\Theta\left({n}\right)$	非原地排序	不稳定	6

[5]字符串

KMP

时空复杂度

时间复杂度为 $\Theta\left({n+m}\right)$ ,空间复杂度为 $\Theta\left({m}\right)$ 。

基本代码

#include<bits/stdc++.h>
using namespace std;
int ans[1000039],lena,lenb; 
char a[1000039],b[1000039];
int main(){
	register int i,j;
	cin>>a>>b;lena=strlen(a);lenb=strlen(b);
	for(i=1;i<lenb;i++){	 
	   while(j&&b[i]!=b[j+1])j=ans[j];	
	   if(b[j+1]==b[i])j++;	
		ans[i]=j;
	}
	j=0;
	for(i=0;i<lena;i++){
		while(j>0&&b[j+1]!=a[i])j=ans[j];
		if(b[j+1]==a[i])j++;
		if(j==lenb){
			printf("%d\n",i-lenb+1);
			j=ans[j];
		}
	}
	for(i=1;i<=lenb;i++)printf("%d ",ans[i]);
	return 0;
}

[6-8]搜索

时间复杂度基本为常数优化。

[6]减枝搜索

[6]记忆化搜索

[7]启发式搜索

[7]双向BFS搜索

[7]迭代加深搜索

[8]搜索对象压缩搜索

[6-7]图论

[6]Prim 和 kruskal 最小生成树

kruskal 时空复杂度

时间复杂度为 $\Theta\left({m\log{m}}\right)$ ,空间复杂度为 $\Theta\left({n+m}\right)$ 。

kruskal 基本代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,f[200039],tot;
struct node{int u,v,w;bool operator<(node x)const{return w<x.w;}}a[200039];
int find(int x){return f[x]=f[x]^x?find(f[x]):x;}
void kruskal(){
	int x,y;
	for(int i=1;i<=m;i++){
		x=find(a[i].u);
		y=find(a[i].v);
		if(x==y) continue;
		else{
			ans+=a[i].w;
			f[x]=y;
			tot++;
			if(tot==n-1) break;
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	register int i,j;
	for(i=1;i<=n;i++)f[i]=i;
	for(i=1;i<=m;i++)scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
	sort(a+1,a+m+1);kruskal();
	if(tot==n-1)printf("%d",ans);
	else printf("orz");
	return 0;
}

[7]次小生成树

[6]Dojkstra、bellman_ford 和 SPFA 单源最短路

[7]单源次短路

[6]Floyd-Warshall 求最短路和传递闭包

[6]DAG拓扑排序

[6]欧拉道路和欧拉回路

[6]二分图构造和判定

[6]最近公共祖先

倍增LCA 时空复杂度

时间复杂度为预处理 $\Theta\left({n\log{树高}}\right)$ ，查询 $\Theta\left({\log{树高}}\right)$ 。

空间复杂度为 $\Theta\left({n\log{树高}}\right)$ 。

倍增LCA 基本代码

#include<bits/stdc++.h>
using namespace std;
int n,m,root,x,y,d[500039];
int Fa[500039][39];
vector<int>v[500039];
void dfs(int u,int deep,int fa){
	d[u]=deep;int k=1;Fa[u][0]=fa;
	do{Fa[u][k]=Fa[Fa[u][k-1]][k-1];}while(Fa[u][k++]);
	for(int i=0;i<v[u].size();i++)if(v[u][i]^fa)dfs(v[u][i],deep+1,u);
}
int LCA(int u,int v){
	int k=19;
	while(d[u]<d[v]){while(d[u]>d[Fa[v][k]]&&k)k--;v=Fa[v][k];}
	if(u==v)return x;k=20;
	while(k--){if(Fa[u][k]!=Fa[v][k])u=Fa[u][k],v=Fa[v][k];}
	return Fa[u][0];
}
int main(){
	scanf("%d%d%d",&n,&m,&root);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(root,0,0);d[0]=-1;
	while(m--){
		scanf("%d%d",&x,&y);
		if(d[x]>d[y])x^=y^=x^=y;
		printf("%d\n",LCA(x,y));
	}
}

[7]求强连通分量

[7]强连通分量缩点

[7]求割点割边

[6-8]动态规划

[6]树形动态规划

[7]状态压缩动态规划

[8]动态规划优化

斜率优化DP

四边形不等式优化DP

二维四边形不等式优化区间DP

CDQ分治优化DP

[5-7]数学知识

[5-6]高中数学

[5]代数

[6]解析几何

[6]立体几何

[5-7]初等数论

[5]同余式

[7]欧拉定理和欧拉函数

欧拉函数

$\varphi(n)$ 表示小于n的正整数与n互质的数的个数。

当n为质数时 $\varphi(n)=n-1$

当n为奇数时 $\varphi(2n)=\varphi(n)$

当 $\gcd(a,b)=1$ 时 $\varphi(ab)=\varphi(a)\varphi(b)$

欧拉定理

当 $\gcd(a,p)=1$ 时 $a^{\varphi(p)}\equiv1(mod\ p)$

[7]费马小定理

$a^{p-1}\equiv1(mod\ p)$

[7]威尔逊定理

当且仅当 $p$ 为素数时 $(p-1)\equiv-1(mod\ p)$ 。

[7]斐蜀定理

当 $a,b\not=0$ 时， $\exists x,y\in \mathbb{Z}$ 满足 $ax+by=\gcd(a,b)$ 。

[7]逆元

当 $\gcd(a,b)\not=0$ 时， $(a/b)mod\ p$ 可转换为 $a*b^{p-2}mod\ p$

[7]扩展欧几里得

[7]中国剩余定理

[6-7]组合数学

[6]可重集排列

对于一个有 $n$ 个元素共 $k$ 种的集合，其中每种元素分别有 $p_1,p_2\cdots p_k$ 个，那么可重集排列数量为

$\frac{n!}{\prod_{i-1}^{k}p_i!}$

[6]可重集组合

对于一个有 $n$ 个元素的集合，每次选 $k$ 个，允许元素重复，且不计顺序的可重集组合数量为

$\left(\begin{array}{}n+r-1\\r\\\end{array}{}\right)$

[6]错排、圆排

错排

一个长度为 $n$ 的排列且满足 $\forall i\in[1,n]$ 第 $i$ 个数不为 $i$ 的数量为

递推式

$D_n=nD_{n-1}+{-1}^n，D_1=0$

通项式

$D_n=\sum_{k=0}^{n}\left(\begin{array}{}n\\k\\\end{array}{}\right)(n-k)!(-1)^k$

圆排

从 $n$ 个元素中选 $r$ 个进行圆排列的数量为

$\frac{n!}{r\times(n-r)!}$

[6]鸽巢原理

[6]二项式定理

$(x+y)^n=\left(\begin{array}{}n\\0\\\end{array}{}\right)x^ny^0+\left(\begin{array}{}n\\1\\\end{array}{}\right)x^{n-1}y^1+\left(\begin{array}{}n\\2\\\end{array}{}\right)x^{n-2}y^2+\cdots\cdots+\left(\begin{array}{}n\\n-1\\\end{array}{}\right)x^1y^{n-1}+\left(\begin{array}{}n\\n\\\end{array}{}\right)x^0y^n\ \ \ {n\in\mathbb{Z^+}}$

$(x+y)^n=\left[\begin{matrix}{}x^0\cdots x^n\\\end{matrix}{}\right]\left[\begin{matrix}{}\left(\begin{matrix}{}n\\0\\\end{matrix}{}\right)&&\\&\ddots&\\&&\left(\begin{matrix}{}n\\n\\\end{matrix}{}\right)\\\end{matrix}{}\right]\left[\begin{matrix}{}&&1\\&\vdots&\\1&&\\\end{matrix}{}\right]\left[\begin{matrix}{}y_0\\\vdots\\y_n\\\end{matrix}{}\right]\ \ \ {n\in\mathbb{Z^+}}$

[7]容斥原理

[7]卡特兰数

$C_{n+1}=C_0C_n+C_1C_{n-1}+\cdots+C_nC_0$

[5-7]线性代数

[5]矩阵概念

[6]特殊矩阵

稀疏矩阵

三角矩阵

[6]矩阵的初等变换

[6]矩阵的加减乘和置换

矩阵加减法

$\left[\begin{matrix}{}a_{1,1}&a_{1,2}&\cdots&a_{1,m}\\a_{2,1}&a_{2,2}\\\vdots&&\ddots&\\a_{n,1}&&&a_{n,m}\\\end{matrix}{}\right]\pm\left[\begin{matrix}{}b_{1,1}&b_{1,2}&\cdots&b_{1,m}\\b_{2,1}&b_{2,2}\\\vdots&&\ddots&\\b_{n,1}&&&b_{n,m}\\\end{matrix}{}\right]=\left[\begin{matrix}{}a_{1,1}\pm b_{1,1}&a_{1,2}\pm b_{1,2}&\cdots&a_{1,m}\pm b_{1,m}\\a_{2,1}\pm b_{2,1}&a_{2,2}\pm b_{2,2}\\\vdots&&\ddots&\\a_{n,1}\pm b_{n,1}&&&a_{n,m}\pm b_{n,m}\\\end{matrix}{}\right]$

矩阵加减法满足交换律和结合律。

矩阵乘法

$C_{n+1}=C_0C_n+C_1C_{n-1}+\cdots+C_nC_0$

$C=A\cdot B\ \ \ \ C_{i,j}=\sum_{k=1}^{p}A_{i,k}B_{k,j}$
$\left[\begin{matrix}{}a_{1,1}&a_{1,2}&\cdots&a_{1,p}\\a_{2,1}&a_{2,2}\\\vdots&&\ddots&\\a_{m,1}&&&a_{m,p}\\\end{matrix}{}\right]\cdot\left[\begin{matrix}{}b_{1,1}&b_{1,2}&\cdots&b_{1,n}\\b_{2,1}&b_{2,2}\\\vdots&&\ddots&\\b_{p,1}&&&b_{p,n}\\\end{matrix}{}\right]=\left[\begin{matrix}{}\sum_{k=1}^{p}a_{1k}b_{k,1}&\sum_{k=1}^{p}a_{1,k}b_{k,2}&\cdots&\sum_{k=1}^{p}a_{1,k}b_{k,n}\\\sum_{k=1}^{p}a_{2,k}b_{k,1}&\sum_{k=1}^{p}a_{2,k}b_{k,2}\\\vdots&&\ddots&\\\sum_{k=1}^{p}a_{m,k}b_{k,1}&&&\sum_{k=1}^{p}a_{m,k}b_{k,n}\\\end{matrix}{}\right]$