第十五届蓝桥杯大赛软件赛知识点大纲_第十五届蓝桥杯大纲

C组

1.枚举

枚举类型的定义：

枚举类型(enumeration)是C++中的一种派生数据类型，它是由用户定义的若干枚举常量的集合。

定义格式：

enum <类型名> {<枚举常量表>};

举例：

enum color {RED, BLUE, WHITE, BLACK}; // 定义枚举类型color_set1

enum week {Sun, Mon, Tue, Wed, Thu, Fri, Sat}; // 定义枚举类型week

2.排序

（1）冒泡排序

（2）选择排序

（3）插入排序

3.搜索(bfs,dfs)

4.贪心

5.模拟

6.二分

7.DP(普通一维问题)

8.高精度

9.数据结构

（1）栈

（2）队列

（3）链表

10.数学

（1）初等数论

B组

11.排序

（1）归并排序

（2）快速排序

（3）桶排序

（4）堆排序

（5）基数排序

12.搜索

（1）剪枝

（2）双向BFS

（3）记忆化搜索

（4）迭代加深搜索

（5）启发式搜索

13.DP

（1）背包DP

（2）树形DP

（3）状压DP

（4）数位DP

（5）DP的常见优化

14.字符串

（1）哈希

（2）kmp

（3）manacher

15.图论

（1）欧拉回路

（2）最小生成树

（3）单源最短路及差分约束系统

（4）拓扑序列

（5）二分图匹配

（6）图的连通性问题（割点、桥、强连通分量）

（7）DFS序

（8）最近共同祖先

16.数学

（1）排列组合

（2）二项式定理

（3）容斥原理

（4）模意义下的逆元

（5）矩阵运算

（6）高斯消元

17.数据结构

（1）ST表

（2）堆

（3）树状数组

（4）线段树

（5）Trie树

（6）并查集

（7）平衡树(利用系统自带的标准库实现简

单平衡树)

18.计算几何

（1）基础计算和基本位置关系判定

（2）概率论

（3）博弈论

A组

19.字符串

（1）AC自动机

（2）拓展kmp

（3）后缀数组

（4）后缀自动机

（5）回文自动机

20.图论

（1）网络流

（2）一般图匹配

21.数学

（1）生成函数

（2）莫比乌斯反演

（3）快速傅里叶变换

22.数据结构

（1）树链剖分

（2）二维/动态开点线段树

（3）平衡树

（4）可持久化数据结构

（5）树套树

（6）动态树