CCF 信息学奥赛提高篇电子书

丛书编委会

FOREWORD 丛书序

PREFACE 前言

第一章 C++程序设计进阶

第一节 STL简介

一、STL的定义与历史

二、STL版本简介

三、如何理解泛型编程

四、STL的六大组件

五、STL的优点

六、本节小结

第二节 STL的容器

一、容器概述

二、序列容器

三、关联容器

四、容器适配器

五、bitset

六、本节小结

第三节 STL的迭代器

一、迭代器的基本概念

二、迭代器的分类

三、迭代器的操作

四、迭代器的使用示例

五、本节小结

第二章 数据结构与算法

第一节 线性结构

一、单调队列

二、ST表

三、本节小结

第二节 集合与并查集

一、集合

二、并查集

三、本节小结

第三节 树及其应用

一、树、森林与二叉树的转换

二、二叉堆及其应用

三、树的简单应用

四、最近公共祖先

五、树状数组

六、线段树

七、笛卡儿树

八、字典树

九、二叉查找树

十、平衡树

十一、本节小结

第四节 图及其应用

一、最小生成树

二、最短路径

三、单源次短路径

四、拓扑排序

五、欧拉路径和欧拉回路

六、强连通分量

七、割点与割边

八、二分图

九、本节小结

第五节 哈希表及其应用

一、数值的哈希

二、冲突的处理

三、字符串哈希

四、数据结构哈希

五、本节小结

第六节 排序算法

一、桶排序

二、快速排序

三、归并排序

四、堆排序

五、基数排序

六、分治算法

七、本节小结

第七节 搜索算法的优化

一、DFS算法回顾

二、DFS算法优化

三、BFS算法回顾

四、BFS算法优化

五、记忆化搜索

六、迭代加深搜索

七、本节小结

第八节 高级动态规划

一、动态规划的基本原理

二、线性动态规划

三、多次动态规划

四、背包动态规划

五、区间动态规划

六、矩阵动态规划

七、状态压缩动态规划

八、树形动态规划

九、状态不满型动态规划

十、动态规划进阶

十一、本节小结

第九节 字符串相关算法

一、字符串匹配朴素算法

二、KMP算法

三、Manacher算法

四、本节小结

第三章 数学在程序设计中的应用

第一节 矩阵的应用

一、矩阵的加减法

二、矩阵的数乘

三、矩阵的乘法

四、稀疏矩阵的存储及其运算

五、线性方程组

六、矩阵的初等行变换

七、高斯消元法

八、矩阵的快速幂算法

九、本节小结

第二节 数论基础

一、函数单调性的应用

二、模线性方程与模线性方程组

三、中国剩余定理

四、本节小结

第三节 概率和期望

一、概率和期望的概念

二、应用实例

三、本节小结

第四节 排列与组合

一、排列

二、组合

三、常用技巧

四、本节小结

第五节 容斥原理

一、基本原理

二、应用实例

三、本节小结

第六节 鸽巢原理

一、基本原理

二、应用实例

三、本节小结

附录 目录结构与NOI考纲的对应关系

推荐阅读