CSP-S初赛基础知识整理

CSP-S初赛基础知识整理

RT

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

[1]计算机基础知识

计算机系统的组成

硬件系统和软件系统。

计算机硬件的五大组成

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

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

[1-2]二进制

[1]基本定义及应用

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

[1]基本运算

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

[2]位运算

1. and(&)

2. or(|)

3. xor(^)

4. not(~)

[1]其他进制及转换

八进制

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

十六进制

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

十进制

有 $0\to 9$ 10个字符组成。
后缀为$\text{D}$。

[1]主要人物及贡献

[5]Linux

time

real time > cpu time = user time + sys time

real time

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

user time

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

sys time

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

gdb

默认

1. gdb ./a

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

2. gdn --args ./a 1.txt

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

其他操作

1. b(reak)

设置断点。

2. display

查看变量或式的值。

3. c(ontinue)

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

4. s(ept)

进入函数调试。

[5]编译选项

默认

g++ 1.cpp -o 1.exe

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

额外编译指令

1. -x language filename

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

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

2. -x none filename

取消上一个指令的效果。

3. -c

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

4. -S

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

5. -o

标记输出文件。

6. -O0,-O1,-O2,-O3

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

7. -g

产生调试信息。

[5]STL

STL

[5-8]算法

[6]复杂度分析

空间复杂度分析

时间复杂度分析

主定理

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

当 $a\ge 1andb>1$ 时

1. 若$\exists ϵ>0$，有$f(n)=O\left(n^{{\log }_{b}a-ϵ}\right)$，则$T(n)=\Theta \left(n^{{\log }_{b}a}\right)$。

2. 若有$f(n)=O\left(n^{{\log }_{b}a}\right)$，则$T(n)=\Theta \left(n^{{\log }_{b}a}\log n\right)$。

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

[6]基础算法

分治算法

[5-6]排序算法

[5]字符串

KMP

时空复杂度

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

基本代码

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

[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
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;
}
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

[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
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));
	}
} 
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
30
31

[7]求强连通分量

[7]强连通分量缩点

[7]求割点割边

[6-8]动态规划

[6]树形动态规划

[7]状态压缩动态规划

[8]动态规划优化

斜率优化DP

四边形不等式优化DP

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

CDQ分治优化DP

[5-7]数学知识

[5-6]高中数学

[5]代数

[6]解析几何

[6]立体几何

[5-7]初等数论

[5]同余式

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

欧拉函数

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

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

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

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

欧拉定理

当 $\gcd (a,p)=1$时 $a^{\phi (p)}\equiv 1(modp)$

[7]费马小定理

$a^{p-1}\equiv 1(modp)$

[7]威尔逊定理

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

[7]斐蜀定理

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

[7]逆元

当 $\gcd (a,b)\ne 0$ 时，$(a/b)modp$ 可转换为 $a\ast b^{p-2}modp$

[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$ 个，允许元素重复，且不计顺序的可重集组合数量为

( n + r − 1 r ) \left(

{}\right) (n+r−1r​)

[6]错排、圆排

错排

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

递推式

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

通项式

D n = ∑ k = 0 n ( n k ) ( n − k ) ! ( − 1 ) k D_n=\sum_{k=0}^{n}\left(

{}\right)(n-k)!(-1)^k Dn​=k=0∑n​(nk​)(n−k)!(−1)k

圆排

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

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

[6]鸽巢原理

[6]二项式定理

( x + y ) n = ( n 0 ) x n y 0 + ( n 1 ) x n − 1 y 1 + ( n 2 ) x n − 2 y 2 + ⋯ ⋯ + ( n n − 1 ) x 1 y n − 1 + ( n n ) x 0 y n     n ∈ Z + (x+y)^n=\left(

{}\right)x^ny^0+\left({}\right)x^{n-1}y^1+\left({}\right)x^{n-2}y^2+\cdots\cdots+\left({}\right)x^1y^{n-1}+\left({}\right)x^0y^n\ \ \ {n\in\mathbb{Z^+}} (x+y)n=(n0​)xny0+(n1​)xn−1y1+(n2​)xn−2y2+⋯⋯+(nn−1​)x1yn−1+(nn​)x0yn   n∈Z+

( x + y ) n = [ x 0 ⋯ x n ] [ ( n 0 ) ⋱ ( n n ) ] [ 1 ⋮ 1 ] [ y 0 ⋮ y n ]     n ∈ Z + (x+y)^n=\left[

{}\right]\left[{}\right)&&\\&\ddots&\\&&\left({}\right)\\\end{matrix}{}\right]\left[{}\right]\left[{}\right]\ \ \ {n\in\mathbb{Z^+}} (x+y)n=[x0⋯xn​]⎣ ⎡​(n0​)​⋱​(nn​)​⎦ ⎤​⎣ ⎡​1​⋮​1​⎦ ⎤​⎣ ⎡​y0​⋮yn​​⎦ ⎤​   n∈Z+

[7]容斥原理

[7]卡特兰数

$$C_{n+1}=C_0{C}_n+C_1{C}_{n-1}+\cdots +C_n{C}_0$$

[5-7]线性代数

[5]矩阵概念

[6]特殊矩阵

稀疏矩阵

三角矩阵

[6]矩阵的初等变换

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

矩阵加减法

[ a 1 , 1 a 1 , 2 ⋯ a 1 , m a 2 , 1 a 2 , 2 ⋮ ⋱ a n , 1 a n , m ] ± [ b 1 , 1 b 1 , 2 ⋯ b 1 , m b 2 , 1 b 2 , 2 ⋮ ⋱ b n , 1 b n , m ] = [ a 1 , 1 ± b 1 , 1 a 1 , 2 ± b 1 , 2 ⋯ a 1 , m ± b 1 , m a 2 , 1 ± b 2 , 1 a 2 , 2 ± b 2 , 2 ⋮ ⋱ a n , 1 ± b n , 1 a n , m ± b n , m ] \left[

{}\right]\pm\left[{}\right]=\left[{}\right] ⎣ ⎡​a1,1​a2,1​⋮an,1​​a1,2​a2,2​​⋯⋱​a1,m​an,m​​⎦ ⎤​±⎣ ⎡​b1,1​b2,1​⋮bn,1​​b1,2​b2,2​​⋯⋱​b1,m​bn,m​​⎦ ⎤​=⎣ ⎡​a1,1​±b1,1​a2,1​±b2,1​⋮an,1​±bn,1​​a1,2​±b1,2​a2,2​±b2,2​​⋯⋱​a1,m​±b1,m​an,m​±bn,m​​⎦ ⎤​

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

矩阵乘法

$$C_{n+1}=C_0{C}_n+C_1{C}_{n-1}+\cdots +C_n{C}_0$$

$$C=A\cdot B{C}_{i,j}=\sum _{k=1}^p{A}_{i,k}{B}_{k,j}$$
[ a 1 , 1 a 1 , 2 ⋯ a 1 , p a 2 , 1 a 2 , 2 ⋮ ⋱ a m , 1 a m , p ] ⋅ [ b 1 , 1 b 1 , 2 ⋯ b 1 , n b 2 , 1 b 2 , 2 ⋮ ⋱ b p , 1 b p , n ] = [ ∑ k = 1 p a 1 k b k , 1 ∑ k = 1 p a 1 , k b k , 2 ⋯ ∑ k = 1 p a 1 , k b k , n ∑ k = 1 p a 2 , k b k , 1 ∑ k = 1 p a 2 , k b k , 2 ⋮ ⋱ ∑ k = 1 p a m , k b k , 1 ∑ k = 1 p a m , k b k , n ] \left[

{}\right]\cdot\left[{}\right]=\left[{}\right] ⎣ ⎡​a1,1​a2,1​⋮am,1​​a1,2​a2,2​​⋯⋱​a1,p​am,p​​⎦ ⎤​⋅⎣ ⎡​b1,1​b2,1​⋮bp,1​​b1,2​b2,2​​⋯⋱​b1,n​bp,n​​⎦ ⎤​=⎣ ⎡​∑k=1p​a1k​bk,1​∑k=1p​a2,k​bk,1​⋮∑k=1p​am,k​bk,1​​∑k=1p​a1,k​bk,2​∑k=1p​a2,k​bk,2​​⋯⋱​∑k=1p​a1,k​bk,n​∑k=1p​am,k​bk,n​​⎦ ⎤​

矩阵乘法满足结合律，不满足交换律。

[6]线性方程组和高斯消元法