信息学奥赛一本通关

第一部分
编程平台介绍
第1 章 图形化编程模块简介  2
1.1 变量  2
1.2 运算符  4
1.3 顺序语句  6
1.4 分支语句  6
1.5 循环语句  8
1.6 函数运算  9
第2 章 Dev-C 简介  10
2.1 Dev-C 界面  10
2.2 快捷键  11
2.3 调试配置  11
2.4 设置断点并查看  12
2.5 编译器与编译日志  13
第二部分
计算机基础知识
第3 章 信息学奥赛简介  16
3.1 NOIP  16
3.2 CSP-J/S 16
3.3 NOI  17
3.4 APIO 和IOI  17
第4 章 计算机硬件基础  18
4.1 计算机发展史  18
4.2 计算机硬件  19
4.2.1 运算器 20
4.2.2 控制器 20
4.2.3 存储器 21
4.2.4 输入设备 21
4.2.5 输出设备 22
4.3 数制与编码  22
4.3.1 二进制与十进制 24
4.3.2 二进制与八进制 25
4.3.3 二进制与十六进制 26
4.3.4 ASCII 编码  27
4.3.5 汉字编码 27
4.3.6 原码、反码、补码 27
4.3.7 位运算 28
4.3.8 多媒体文件的数字化 30
第5 章 操作系统与应用软件  32
5.1 DOS 操作系统  32
5.2 Windows 操作系统及软件  34
5.3 Linux 操作系统 34
第6 章 计算机网络基础  35
6.1 计算机网络组成  35
6.2 计算机网络类型  37
6.3 IP 地址  38
6.4 网络安全  39
第三部分
从图形化编程到C 入门
第7 章 C 基础  42
7.1 数据类型  42
7.2 语法  46
7.2.1 程序入口 46
7.2.2 注释 47
7.2.3 变量定义及使用 47
7.2.4 语句结束符 48
7.2.5 语句块与缩进 48
7.2.6 作用域 48
7.2.7 常量与转义字符 49
7.3 运算符  51
7.3.1 算术运算符 51
7.3.2 关系运算符 53
7.3.3 逻辑运算符 53
7.3.4 赋值运算符 53
7.3.5 三目运算符 54
7.4 输入、输出  54
7.4.1 输入、输出流 55
7.4.2 格式化输入、输出 55
7.4.3 文件输入、输出 57
第8 章 程序三大基本结构  60
8.1 顺序结构  60
8.2 分支结构  64
8.2.1 if-else 结构  65
8.2.2 switch-case 结构 69
8.3 循环结构  72
8.3.1 for 循环  73
8.3.2 while 循环  76
8.3.3 do-while 循环 79
第9 章 数组  81
9.1 一维数组  81
9.2 二维数组  88
第10 章 自定义函数与指针  95
10.1 自定义函数 95
10.2 内联函数 96
10.3 指针 96
10.4 函数的参数传递 97
10.4.1 按值传递  97
10.4.2 地址传递  99
10.4.3 指针传递  100
10.5 递归 101
10.6 数组传递参数 105
10.6.1 一维数组传递参数  105
10.6.2 二维数组传递参数  107
第11 章 结构体  110
11.1 结构体的定义与初始化 110
11.2 结构体的调用 111
11.3 运算符重载 113
第四部分
数学知识基础
第12 章 数论  118
12.1 整除理论（CSP-J）  118
12.1.1 定义及性质  118
12.1.2 奇数与偶数  119
12.2 同余理论（CSP-S）  120
12.3 素数（CSP-J/S）  122
12.4 最大公约数（CSP-S）  128
12.4.1 辗转相除法  128
12.4.2 二进制算法  130
12.5 最小公倍数（CSP-S）  131
12.6 扩展欧几里得法（CSP-S）  133
12.7 快速幂算法（CSP-J/S）  135
12.8 逆元（CSP-S）  136
12.8.1 扩展欧几里得法求逆元  137
12.8.2 费马小定理求逆元  138
12.8.3 线性算法/ 递归求逆元  140
12.9 中国剩余定理（CSP-S）  142
12.10 斐波那契数列（CSP-S）  144
12.11 卡特兰数（CSP-S）  147
第13 章 组合数学  151
13.1 排列（CSP-J/S）  151
13.1.1 选排列  151
13.1.2 全排列  154
13.1.3 错位排列  154
13.1.4 循环排列  157
13.2 组合（CSP-J/S）  157
13.2.1 重复组合  158
13.2.2 不相邻组合  159
13.3 计数原理（CSP-J）  161
13.3.1 加法原理（分类加法计数原理）  161
13.3.2 乘法原理（分步乘法计数原理）  162
13.4 抽屉原理/ 鸽巢原理（CSP-J）  163
13.5 容斥原理（CSP-J）  165
13.6 母函数（CSP-S）  166
13.6.1 普通型母函数  167
13.6.2 指数型母函数  172
第14 章 概率论（CSP-S）  176
14.1 基础知识 176
14.1.1 样本空间与随机事件 176
14.1.2 事件的概率  179
14.2 随机变量 180
14.3 期望 182
第15 章 计算几何（CSP-S）  185
15.1 基础知识 185
15.1.1 平面直角坐标系  185
15.1.2 点、直线、线段  186
15.1.3 圆与多边形  186
15.1.4 矢量  188
15.2 计算几何C 模型  190
15.2.1 计算点、点关系  190
15.2.2 计算点、线关系  193
15.2.3 计算线、线（矢量）关系  198
15.2.4 圆与多边形  202
15.3 平面凸包 211
15.3.1 判断凸多边形  211
15.3.2 凸多边形重心  213
15.3.3 寻找凸包—Graham算法  216
15.4 旋转卡壳 220
15.4.1 基础概念  220
15.4.2 凸多边形直径  221
15.4.3 凸多边形宽度  226
15.4.4 凸多边形间最大距离 227
15.4.5 凸多边形间最小距离 232
15.4.6 凸多边形外接矩形最小面积  238
15.4.7 凸多边形外接矩形最小周长  244
第16 章 线性代数（CSP-J/S） 245
16.1 行列式 245
16.2 矩阵 246
16.2.1 矩阵的加法  248
16.2.2 数与矩阵的乘法  248
16.2.3 矩阵与矩阵的乘法  249
16.2.4 逆矩阵  249
16.2.5 分块矩阵  250
16.3 矩阵的初等变换 252
16.4 求解线性方程组 253
16.4.1 高斯消元法  253
16.4.2 LU 分解法 259
第17 章 函数（CSP-J/S）  267
17.1 定义 267
17.2 基本性质 267
17.2.1 有界性  267
17.2.2 单调性  267
17.2.3 奇偶性  268
17.2.4 周期性  268
17.3 初等函数 268
第五部分
数据结构
第18 章 时间、空间复杂度  274
18.1 时间复杂度 274
18.1.1 常数阶O(1)  274
18.1.2 线性阶O(n)  275
18.1.3 对数阶O(log2n) 275
18.1.4 线性对数阶O(n log2n) 276
18.1.5 幂指数阶O(na)  276
18.1.6 时间复杂度曲线对比 276
18.2 空间复杂度 277
第19 章 STL 简介 278
19.1 迭代器 278
19.2 容器 279
19.2.1 序列容器  279
19.2.2 关联容器  287
19.3 容器适配器 292
19.3.1 queue 适配器 292
19.3.2 stack 适配器  294
19.3.3 priority_queue适配器  295
19.4 算法 297
19.4.1 非可变序列算法  298
19.4.2 可变序列算法  300
19.4.3 排序及相关算法  303
19.4.4 数值算法  307
第20 章 线性数据结构  310
20.1 顺序存储线性表 310
20.2 链表 312
20.2.1 单链表  312
20.2.2 静态链表  318
20.2.3 循环链表  318
20.2.4 双链表  319
20.3 队列 322
20.4 栈 329
第21 章 树  333
21.1 树的一般概念 333
21.1.1 结点关系  333
21.1.2 度与深度  334
21.1.3 树的遍历  335
21.2 二叉树 339
21.2.1 二叉树性质  340
21.2.2 二叉树结构与操作  340
21.2.3 遍历二叉树  345
21.2.4 二叉排序树  350
21.2.5 平衡二叉树  357
21.3 树状数组 363
21.3.1 前缀和  363
21.3.2 树状数组思想  364
21.3.3 lowbit 算法 365
21.3.4 单点更新  366
21.3.5 区间求和  366
21.4 线段树 369
21.4.1 线段树基本结构  369
21.4.2 建立线段树  371
21.4.3 单点更新  372
21.4.4 区间查询与修改  373
21.5 并查集 382
21.5.1 基本操作  382
21.5.2 算法优化  383
21.6 哈夫曼树 387
21.6.1 构建哈夫曼树  387
21.6.2 哈夫曼树的实现  388
21.6.3 哈夫曼编码  391
第22 章 图论  392
22.1 图的重要概念 392
22.2 欧拉路与欧拉回路 393
22.3 连通图 401
22.3.1 广度优先算法  402
22.3.2 强连通图  406
22.3.3 割点与桥  411
22.4 哈密尔顿图 415
22.5 最短路径 420
22.5.1 Floyed 算法  422
22.5.2 Dijkstra 算法  426
22.5.3 Bellman-Ford 算法  431
22.5.4 SPFA 算法 433
22.6 最小生成树 437
22.6.1 Prim 算法  437
22.6.2 Kruskal 算法  445
22.7 关键路径 449
22.7.1 相关概念  450
22.7.2 拓扑排序  451
22.7.3 关键路径的应用  455
第六部分
算法补充与归纳
第23 章 数学公式补充  464
23.1 蔡勒公式 464
23.2 归一问题 465
23.3 等差数列 465
23.4 等比数列 467
第24 章 高精度四则运算  468
24.1 数字存储 468
24.2 高精度加法计算 469
24.3 高精度减法计算 472
24.4 高精度乘法计算 476
24.5 高精度除法计算 478
第25 章 字符串算法  484
25.1 哈希算法 484
25.2 KMP 算法  488
25.3 Trie 树 494
25.4 Manacher 算法 498
25.5 AC 自动机  502
第26 章 排序算法  508
26.1 冒泡排序算法 508
26.2 插入排序算法 510
26.3 选择排序算法 512
26.4 快速排序算法 513
26.5 归并排序算法 516
26.6 桶排序算法 519
26.7 堆排序算法 521
第27 章 搜索算法  522
27.1 A* 算法  522
27.2 回溯算法 531
27.2.1 解空间树  531
27.2.2 回溯算法框架  540
第28 章 贪心算法  543
28.1 区间问题 543
28.1.1 最多不相交区间问题 543
28.1.2 选点问题  546
28.1.3 区间覆盖问题  548
28.2 部分背包问题 551
28.3 种树问题 553
第29 章 分治算法  558
29.1 汉诺塔问题 558
29.2 二分查找算法 561
29.3 主定理 563
29.4 Strassen 算法  567
29.5 循环赛日程表问题 570
第30 章 动态规划算法  574
30.1 资源分配问题 575
30.2 最长递增/ 递减子序列问题 579
30.3 项链问题 582
30.4 双线动态规划问题 585
第七部分
2019—2022 年CSP-JS 真题及参考答案
2019 CCF 非专业级别软件能力认证
第一轮（CSP-J）  590
2019 CCF 非专业级别软件能力认证第一轮
（CSP-J）参考答案 600
2019 CCF 非专业级别软件能力认证
第一轮（CSP-S）  601
2019 CCF 非专业级别软件能力认证
第一轮（CSP-S）参考答案 613
2020 CCF 非专业级别软件能力认证
第一轮（CSP-J）  614
2020 CCF 非专业级别软件能力认证
第一轮（CSP-J）参考答案 625
2020 CCF 非专业级别软件能力认证
第一轮（CSP-S）  626
2020 CCF 非专业级别软件能力认证
第一轮（CSP-S）参考答案 640
2021 CCF 非专业级别软件能力认证
第一轮（CSP-J）  641
2021 CCF 非专业级别软件能力认证
第一轮（CSP-J）参考答案 653
2021 CCF 非专业级别软件能力认证
第一轮（CSP-S）  654
2021 CCF 非专业级别软件能力认证
第一轮（CSP-S）参考答案 670
2022 CCF 非专业级别软件能力认证
第一轮（CSP-J）  671
2022 CCF 非专业级别软件能力认证
第一轮（CSP-J）参考答案 683
2022 CCF 非专业级别软件能力认证
第一轮（CSP-S）  684
2022 CCF 非专业级别软件能力认证
第一轮（CSP-S）参考答案 697