NOI 大纲提高级教程

C++面向对象、STL、高级数据结构与算法、数学进阶

简介

本网站严格按照 NOI 提高级大纲 组织内容,包含 5 大模块:基础知识与编程环境、C++程序设计、数据结构、算法、数学与其他。通过交互式动画与代码对照,帮助学习者深入理解高级算法与数据结构的核心概念。

💻

1. 基础知识与编程环境

Linux 终端命令
文件与目录操作、常用命令
已完成 难度 ★★★★★
Linux 文本编辑工具
vim、nano、VSCode 使用
已完成 难度 ★★★★★
g++ 编译命令
编译选项与优化
已完成 难度 ★★★★★
time 命令
查看程序运行时间
已完成 难度 ★★★★★
GDB 调试工具
断点、单步执行、变量查看
已完成 难度 ★★★★★
⌨️

2. C++ 程序设计

🎯

2.1 面向对象特性

面向对象:类
类的概念与简单应用
已完成 难度 ★★★★★★
成员函数与运算符重载
方法定义与运算符自定义
已完成 难度 ★★★★★★
📦

2.2 STL 模板

容器和迭代器
vector, list, deque 等容器
已完成 难度 ★★★★★
对 (pair) 与元组 (tuple)
STL 复合数据类型
已完成 难度 ★★★★★
集合 (set) 与多重集合 (multiset)
有序集合及其操作
已完成 难度 ★★★★★
双端队列 (deque) 与优先队列
双端操作与堆结构
已完成 难度 ★★★★★
映射 (map) 与多重映射 (multimap)
键值对存储与查询
已完成 难度 ★★★★★
位集合 (bitset)
高效的位操作容器
已完成 难度 ★★★★★
算法模板库中的常用函数
常用算法函数演示
已完成 难度 ★★★★★
📦

3. 数据结构

📊

3.1 线性结构

双端栈
两端均可进出的栈
已完成 难度 ★★★★★
单调队列
滑动窗口最大值等应用
已完成 难度 ★★★★★
ST 表 (Sparse Table)
静态区间最值查询
已完成 难度 ★★★★★★
🌲

3.2 集合与森林

并查集
动态连通性问题
已完成 难度 ★★★★★★
树的孩子兄弟表示法
二叉链表表示树
已完成 难度 ★★★★★★
🌳

3.3 特殊树

二叉堆
优先队列的底层实现
已完成 难度 ★★★★★★
树状数组 (Fenwick Tree)
高效的前缀和查询与更新
已完成 难度 ★★★★★★
线段树
区间查询与修改的数据结构
已完成 难度 ★★★★★★
字典树 (Trie)
高效的字符串搜索
已完成 难度 ★★★★★★
笛卡尔树
由序列构建的二叉搜索树
已完成 难度 ★★★★★★★
平衡树 (AVL/Treap/Splay)
自平衡二叉搜索树
已完成 难度 ★★★★★★★★
🔗

3.4 常见图

稀疏图
邻接表与链式前向星表示
已完成 难度 ★★★★★★
二分图 (偶图)
二分图的判定与应用
已完成 难度 ★★★★★★
欧拉图
欧拉路径与回路
已完成 难度 ★★★★★★
有向无环图 (DAG)
拓扑排序与动态规划
已完成 难度 ★★★★★★
强连通分量
Kosaraju/Tarjan 算法
已完成 难度 ★★★★★★★
割点与割边
图中的关键边和关键点
已完成 难度 ★★★★★★★
🗂️

3.5 哈希表

数值哈希函数构造
常见的哈希函数构造
已完成 难度 ★★★★★
字符串哈希函数构造
字符串匹配的哈希方法
已完成 难度 ★★★★★★
哈希冲突的常用处理方法
拉链法与开放寻址法
已完成 难度 ★★★★★★
🌲

3.6 树论基础

树的重心、直径、DFS序与欧拉序
树的常用性质
已完成 难度 ★★★★★★
树上差分、子树和与倍增
树上的区间操作
已完成 难度 ★★★★★★
最近公共祖先 (LCA)
树上两点最近公共节点
已完成 难度 ★★★★★★
⚡

4. 算法

📈

4.1 复杂度分析

时间复杂度分析
时间复杂度的分析方法
已完成 难度 ★★★★★★
空间复杂度分析
空间复杂度的分析方法
已完成 难度 ★★★★★★
🔧

4.2 算法策略

离散化
将大范围值映射到小范围
已完成 难度 ★★★★★★
扫描线算法
矩形面积并等几何问题
已完成 难度 ★★★★★★★
🔀

4.3 基础算法

分治算法
归并排序、快速排序等
已完成 难度 ★★★★★★
📊

4.4 排序算法

归并排序
分治排序算法演示
已完成 难度 ★★★★★
快速排序
快速排序算法演示
已完成 难度 ★★★★★
堆排序
基于堆的排序算法
已完成 难度 ★★★★★★
桶排序
分布式排序算法
已完成 难度 ★★★★★
基数排序
按位排序算法
已完成 难度 ★★★★★★
🔤

4.5 字符串算法

字符串匹配:KMP算法
字符串匹配算法
已完成 难度 ★★★★★★
Manacher算法
最长回文子串线性算法
已完成 难度 ★★★★★★★
🔍

4.6 搜索算法

记忆化搜索
带缓存的递归搜索
已完成 难度 ★★★★★★
启发式搜索 (A*)
使用启发式函数优化搜索
已完成 难度 ★★★★★★★
双向广度优先搜索
两端同时搜索的最短路径
已完成 难度 ★★★★★★★
迭代加深搜索 (IDS)
深度递增的 DFS
已完成 难度 ★★★★★★★
🔗

4.7 图论算法

最小生成树:Prim和Kruskal等算法
Prim 和 Kruskal 算法
已完成 难度 ★★★★★★
单源最短路:Bellman-Ford、Dijkstra、SPFA等算法
Bellman-Ford、Dijkstra、SPFA
已完成 难度 ★★★★★★
单源次短路
第二短路径问题
已完成 难度 ★★★★★★★
Floyd-Warshall算法
多源最短路算法
已完成 难度 ★★★★★★
有向无环图的拓扑排序
DAG 的线性排序
已完成 难度 ★★★★★★
欧拉道路和欧拉回路
一笔画问题
已完成 难度 ★★★★★★
二分图的判定
二分图的判定与应用
已完成 难度 ★★★★★★
强连通分量
Kosaraju/Tarjan 算法
已完成 难度 ★★★★★★★
割点、割边
图中的关键边 and 关键点
已完成 难度 ★★★★★★★
🌲

4.8 树论算法

树的重心、直径、DFS序与欧拉序
树的常用性质
已完成 难度 ★★★★★★
树上差分、子树和与倍增
树上的区间操作
已完成 难度 ★★★★★★
最近公共祖先
树上两点最近公共节点
已完成 难度 ★★★★★★
💡

4.9 动态规划

多维动态规划
二维及更高维的 DP
已完成 难度 ★★★★★★
搜索的剪枝优化
可行性剪枝与最优性剪枝
已完成 难度 ★★★★★★
树型动态规划
在树上进行 DP
已完成 难度 ★★★★★★
状态压缩动态规划
用二进制表示状态
已完成 难度 ★★★★★★★
动态规划的常用优化
斜率优化、四边形不等式等
已完成 难度 ★★★★★★★★
📐

5. 数学与其他

📐

5.1 初等数学

代数(高中部分)
函数、方程、不等式
已完成 难度 ★★★★★
几何(高中部分)
平面几何与立体几何
已完成 难度 ★★★★★★
🔢

5.2 初等数论

同余式
模运算基础
已完成 难度 ★★★★★
欧拉定理和欧拉函数
φ(n) 与相关定理
已完成 难度 ★★★★★★★
费马小定理
模素数的重要定理
已完成 难度 ★★★★★★★
威尔逊定理
素数判定的充分条件
已完成 难度 ★★★★★★★
裴蜀定理
线性方程整数解
已完成 难度 ★★★★★★★
模运算意义下的逆元
模意义下的除法
已完成 难度 ★★★★★★★
扩展欧几里得算法
求方程的整数解
已完成 难度 ★★★★★★★
中国剩余定理
模线性方程组
已完成 难度 ★★★★★★★
🎲

5.3 离散与组合数学

多重集合
允许重复元素的集合
已完成 难度 ★★★★★★
等价关系与等价类
等价关系的基本性质
已完成 难度 ★★★★★★
多重集上的排列
有重复元素的排列
已完成 难度 ★★★★★★
多重集上的组合
有重复元素的组合
已完成 难度 ★★★★★★
错排列、圆排列
特殊排列问题
已完成 难度 ★★★★★★
鸽巢原理
抽屉原理及其应用
已完成 难度 ★★★★★★
二项式定理
杨辉三角与组合数
已完成 难度 ★★★★★★
容斥原理
集合计数的容斥方法
已完成 难度 ★★★★★★★
卡特兰(Catalan)数
重要的组合数列
已完成 难度 ★★★★★★★
📊

5.4 线性代数

向量与矩阵的概念
基本概念与运算
已完成 难度 ★★★★★
矩阵的运算:加法、减法、乘法与转置
加减乘与转置
已完成 难度 ★★★★★★
矩阵的初等变换
矩阵的基本变换操作
已完成 难度 ★★★★★★
特殊矩阵的概念:单位阵、三角阵、对称阵和稀疏矩阵
单位阵、三角阵、对称阵、稀疏矩阵
已完成 难度 ★★★★★★
高斯消元法
解线性方程组
已完成 难度 ★★★★★★★