信奥C++课程大纲

一、准备软件:Dev C++下载与安装
首先掌握 Dev_C++ 的使用,学习C++课程3个月后,再学会CodeBlocks的使用。
二、准备打字能力有一定的盲打能力,不能则进行训练。让打字速度跟得上自己的思考速度。点此进入代码模板打字练习
三、知识板块参考《信息学奥赛考试大纲》
语法
计算机常识
基础算法
数据结构
搜索
动态规划
图论
数学

Level 1:
计算机的基础 ⊙视频
变量的定义与使用 基本数据类型(整型、浮点型、字符型、布尔型)
控制语句结构(顺序、选择、循环)
基本运算(算术运算、关系运算、逻辑运算)
输入输出语句
目标:掌握顺序、循环、分支的简单程序结构,可以使用集成开发环境进行编程与调试,通过编程基础知识的学习,完成单一功能的程序设计。

Level 2:
计算机的存储 ⊙视频⊙ 计算机网络与安全
程序设计语言的特点 计算机软件系统
流程图的概念与描述
ASCII编码
数据类型的转换
多层分支/循环结构
常用数学函数(绝对值函数、平方根函数、max 函数、min 函数)
目标:掌握程序基本设计,能够使用简单数学函数。可以独立完成包含分支语句、循环语句等比较综合的案例,可以使用分支循环嵌套结构。

Level 3
进制转换(二进制、八进制、十进制、十六进制) ⊙视频
数据编码(原码、反码、补码) ⊙视频
位运算(&、|、~、^、<<、>>) ⊙视频
算法的概念与描述(自然语言描述、流程图描述、伪代码描述)
一维数组基本应用 字符数组
枚举法
模拟法
目标:掌握数据编码、进制转换、位运算等知识,掌握一维数组、字符串及函数的使用,能够独立使用模拟法、枚举法解决对应的算法问题。

Level 4:
函数的定义与调用 形参与实参、作用域、函数参数传递的概念(值传递、引用传递、指针传递)
指针类型的概念及基本应用 ⊙视频
结构体
二维数组与多维数组基本应用 动态数组vector ⊙vector视频⊙ ⊙pair视频⊙ ⊙map视频
递推 一维前缀和 一维差分
排序概念和稳定性 排序算法(冒泡排序、插入排序、选择排序)
简单算法复杂度的估算(含多项式、指数复杂度)
文件重定向与文件读写操作
异常处理
目标:掌握函数的定义、调用及函数参数传递的方法;掌握二维数组与多维数组的使用技巧;掌握常用排序算法、文件读写和异常处理的使用。能够解决递推相关问题。

Level 5:
初等数论
数组模拟高精度加法、减法、乘法、除法 二维前缀和 二维差分
单链表、双链表、循环链表
辗转相除法(也称欧几里得算法)
素数表的埃氏筛法和线性筛法
唯一分解定理
二分查找/二分答案(也称二分枚举法) 双指针
贪心算法
分治算法(归并排序和快速排序)
递归
算法复杂度的估算(含多项式、指数、对数复杂度)
目标:掌握初等数论,线性表的知识,二分法、分治法、贪心法的思想,完成指定功能的程序。C++掌握数组模拟高精度计算。

Level 6:
树的定义,构造与遍历 二叉树
哈夫曼树 堆和优先队列
完全二叉树
二叉排序树
哈弗曼编码
格雷编码
深度优先搜索算法 宽度优先搜索算法(也称广度优先搜索算法)
二叉树的搜索算法
简单动态规划(一维动态规划、简单背包问题)
面向对象的思想
类的创建
栈、队列、循环队列
目标:掌握树的基础知识,能够分辨不同的树,并根据不同的搜索算法进行遍历,掌握简单线性动态规划和简单背包问题。

Level 7:
数学库常用函数(三角、对数、指数)
复杂动态规划(二维动态规划、动态规划最值优化)
图的定义及遍历 图论基本算法(图的深度优先遍历、广度优先遍历、泛洪算法) 欧拉路 并查集
表达式计算
单调栈和单调队列
目标:掌握图的定义与遍历相关算法,掌握图论基本概念及基础算法,能使用二维动态规划、动态规划最值优化的知识完成复杂的动态规划算法。

Level 8:
计数原理 排列与组合
杨辉三角
倍增法 快速幂
代数与平面几何(初中数学部分)
图论算法及综合应用(最小生成树、单源最短路) 拓扑排序
较复杂算法的空间复杂度和时间复杂度 算法优化
字符串哈希 哈希表 离散化 Trie字典树
倍增RMQ 倍增LCA
目标:掌握组合数学中基本知识,通过算法的时间和空间效率分析,可以完成相对应的算法优化。

Level 9:达到Level 8 八十分以上水平,正式上路成为专业级选手,可征战CSP-S(提高级,以高中生为主)和NOIP级别的比赛
树状数组 线段树
深搜剪枝 广搜优化
树上差分 平衡树Treap 树链剖分
SPFA算法的优化 差分约束系统 强连通分量 割点和桥 二分图 网络流
KMP算法 AC自动机
数位DP 状态压缩DP 单调优化DP 斜率优化DP
同余问题 矩阵乘法 博弈论 概率期望