跳转至

曲阜夫子学校信息学竞赛 Wiki

欢迎来到曲阜夫子学校的信息学竞赛学习园地，下面是根据NOI大纲编纂的知识点汇总

持续更新中...

最近更新

最近更新
  1. CSP-S第一轮复习题
  2. 算法模板（入门级）
  3. 算法模板（提高级）
  4. 倍增表（ST表）
  5. 线段树与树状数组
  6. 栈
  7. 简单图
  8. 筛法及其应用

入门级

计算机基础与编程环境

计算机基础与编程环境
  1. 计算机的基本构成（CPU、内存、I/O设备等）
  2. Windows、Linux等操作系统的基本概念及其常见操作
  3. 计算机网络和Internet的基本概念
  4. 计算机的历史及其在现代社会中的常见应用
  5. NOI以及相关活动的的历史
  6. 进制的基本概念与进制转换、字节与字
  7. 程序设计语言以及程序编译和运行的基本概念
  8. 使用图形界面创建、复制、删除、移动文件或者目录
  9. 使用Windows系统下的集成开发环境（例如Dev-C++等）
  10. 使用Linux系统下的集成开发环境（例如Code::Blocks等）
  11. g++、gcc等常见编译器的基本使用

C++程序设计

C++程序设计

  1. 程序基本概念

  2. 基本数据类型

    • 整数型：int, long long
    • 实数型：float, double
    • 字符型：char
    • 布尔型：bool

  3. 程序基本语句

    • cin语句，scanf语句，cout语句，printf语句，赋值语句，复合语句
    • if语句，switch语句，多层条件语句
    • for语句，while语句，do while语句
    • 多层循环语句

  4. 基本运算

    • 算术运算：加、减、乘、除、整除、求余
    • 关系运算：大于，大于等于，小于，小于等于，等于，不等于
    • 逻辑运算：与（&&）、或（||）、非（!）
    • 变量自增与自减运算
    • 三目运算
    • 位运算：与（&）、或（|）、非（~）、异或（^）、左移（<<）、右移（>>）

  5. 数学库常用函数

    • 绝对值函数、四舍五入函数、取上整函数、取下整函数、常用三角函数、对数函数、指数函数、平方根函数

  6. 结构化程序设计

    • 顺序结构、分支结构和循环结构
    • 自顶向下、逐步求精的模块坏程序设计
    • 流程图的概念及流程图描述

  7. 数组

    • 数据的定义，数组与数组下标的含义
    • 数组的读入与输出
    • 纯一维数组的综合运用
    • 纯二维数组与多维数组的综合运用

  8. 字符串的处理

    • 字符数组与字符串的关系
    • 字符数组的综合应用
    • string类的定义、相关函数引用
    • string类的综合应用

  9. 函数与递归

    • 函数定义与调用，形参与实参
    • 传值参数与传引用参数
    • 常量与变量的作用范围
    • 递归函数的概念、定义与调用

  10. 结构体类型

  11. 指针类型

    • 指针的概念及调用
    • 指针与数组
    • 字符指针与string类
    • 指向结构体的指针

  12. 文件及基本读写

    • 文件的基本概念，文本文件的基本操作
    • 文本文件类型与二进制文件类型
    • 文件重定向、文件读写等操作

  13. STL模板应用

    • <algorithm>中sort函数
    • 栈（stack）、队列（queue）、链表（list）、向量（vector）等容器

数据结构

数据结构

  1. 线性表

    • 链表：单链表、双向链表、循环链表
    • 栈
    • 队列

  2. 简单树

    • 树的定义及其相关概念
    • 树的父亲表示法
    • 二叉树的定义及其基本性质
    • 二叉树的孩子表示法
    • 二叉树的遍历：前序、中序、后序遍历

  3. 特殊树

    • 完全二叉树的定义与基本性质
    • 完全二叉树的数组表示法
    • 哈夫曼树的定义、构造及其遍历
    • 二叉排序树的定义、构造及其遍历

  4. 简单图

算法

算法

  1. 算法概念与描述

    • 算法概念
    • 算法描述：自然语言描述、流程图描述、伪代码描述

  2. 入门算法

    • 枚举法
    • 模拟法

  3. 基础算法

    • 贪心法
    • 递推法
    • 递归法
    • 二分法
    • 倍增法

  4. 数值处理算法

    • 高精度的加法
    • 高精度的减法
    • 高精度的乘法
    • 求高精度整数除以单精度整数的商和余数

  5. 排序算法

    • 排序算法的基本概念（稳定性等）
    • 冒泡排序
    • 简单选择排序
    • 简单插入排序

  6. 图论算法

    • 图的深度优先遍历算法
    • 图的宽度优先遍历算法
    • 洪水填充算法（floodfill）

  7. 动态规划

    • 动态规划的基本思路
    • 简单一维动态规划
    • 简单背包类型动态规划
    • 简单区间类型动态规划

数学

数学

  1. 数及其运算

    • 数的概念，算术运算（加、减、乘、除、求余）
    • 数的进制：二进制、八进制、十六进制和十进制及其转换
    • 编码：ASCII码，哈夫曼码，格雷码

  2. 初中数学

    • 初中代数
    • 初中平面几何

  3. 初等数论

  4. 组合数学

    • 加法原理
    • 乘法原理
    • 排列及计算公式
    • 组合及计算公式
    • 杨辉三角公式

提高级

计算机基础知识与编程环境

计算机基础知识与编程环境
  1. 在Linux系统终端中使用mkdir、cp、rm、mv等命令新建、复制、删除、移动文件或目录
  2. 在Linux系统终端中使用cd、pwd、ls等命令更改、显示目录路径和查看目录中的文件
  3. 在Linux系统下使用Gedit、Vim或Emacs等文本编辑工具编写代码
  4. 熟悉g++、gcc等编译器以及优化、数学库等常见编译选项
  5. 在Linux系统终端中运行程序，并使用time命令查看程序用时（区分real time、sys time和user time）
  6. 了解调试工具gdb及其break、display、continue、step等命令

C++程序设计

C++程序设计

  1. 类（class）

    • 类的概念及简单应用
    • 成员函数和运算符重载

  2. STL模板

    • 集合（set）
    • 列表（list），双端队列（deuqe），优先队列（priority_queue）
    • 多重集合（multiset）
    • 映射（map），多重映射（multimap）
    • 对（pair），元组（tuple）

数据结构

数据结构

  1. 线性结构

  2. 集合与森林

    • 等价类
    • 并查集
    • 树与二叉树的转化——孩子兄弟表示法

  3. 特殊树

    • 线段树与树状数组
    • 字典树（trie树）
    • 笛卡尔树
    • 二叉平衡树AVL、treap、splay等
    • 基环树

  4. 常见图

    • 稀疏图
    • 偶图（二分图）
    • 欧拉图
    • 有向无环图
    • 连通图与强连通图
    • 重连通图

  5. 哈希表

    • 数值哈希函数构造
    • 排列哈希函数构造
    • 字符串哈希函数构造
    • 哈希函数冲突的常用解决办法

算法

算法

  1. 复杂度分析

    • 空间复杂度分析
    • 时间复杂度分析

  2. 基础算法

    • 分治算法

  3. 排序算法

    • 归并排序
    • 快速排序
    • 堆排序
    • 树形选择排序（锦标赛排序）
    • 桶排序
    • 基数排序

  4. 字符串相关算法

    • 字符串匹配算法——KMP

  5. 搜索算法

    • 搜索的剪枝优化
    • 记忆化搜索
    • 启发式搜索
    • 双向宽度优先搜索
    • 迭代加深搜索
    • 搜索对象的压缩存储

  6. 图论算法

    • Prim和kruskal等求最小生成树算法
    • 求次小生成树算法
    • Dijkstra、bellman_ford、SPFA等求单源最短路算法
    • 求单源次短路径算法
    • Floyd-Warshall算法求任意两点间的最短路和传递闭包
    • 有向无环图的拓扑排序算法
    • 求欧拉道路和欧拉回路算法
    • 二分图的构造及其判定算法
    • 最近公共祖先
    • 求强连通分量算法
    • 强连通分量的缩点算法
    • 求割点、割边算法

  7. 动态规划

    • 树型动态规划
    • 状态压缩动态规划
    • 动态规划的常用优化

数学

数学

  1. 高中数学

    • 代数
    • 解析几何
    • 立体几何

  2. 初等数论

    • 同余式
    • 欧拉定理和欧拉函数
    • 费马小定理
    • 威尔逊定理
    • 裴蜀定理
    • 逆元
    • 扩展欧几里得算法
    • 孙子定理（中国剩余定理）

  3. 组合数学

    • 可重集排列
    • 可重集组合
    • 错排列、圆排列
    • 鸽巢原理
    • 二项式定理
    • 容斥原理
    • 卡特兰数

  4. 线性代数

    • 矩阵概念
    • 特殊矩阵：稀疏矩阵、三角矩阵、对称矩阵
    • 矩阵的初等变换
    • 矩阵的加减乘和转置运算
    • 线性方程组的高斯消元法

NOI 级

C++程序设计

C++程序设计
  1. STL模板：容器（containers）、迭代器（iterators）、空间配置器（allocators）、配接器（adapters）、算法（algorithms）、仿函数（functors）
  2. 面向对象的程序设计思想（OOP）

数据结构

数据结构

  1. 线性结构

    • 分块
    • 块状链表

  2. 序列

    • 后缀数组
    • 跳跃表
    • 无根树的Prufer序列

  3. 复杂树

    • 树链剖分
    • 主席树
    • 二维线段树
    • 后缀树
    • 树套树
    • k-d树
    • 最小树形图
    • 动态树（LCT）

  4. 可合并堆

    • 左偏树
    • 二项堆

  5. 可持久化数据结构

算法

算法

  1. 算法策略

    • 复杂分治思想
    • 平衡规划思想
    • 构造思想

  2. 字符串算法

    • 求最长回文串的Manacher算法
    • 多模匹配算法——AC自动机
    • 求字符串前缀和后缀算法——扩展KMP
    • 确定性有穷自动机——DFA算法
    • 非确定性有穷自动机——NFA算法
    • 后缀自动机

  3. 图论算法

    • 网络流算法
    • 图的支配集、独立集与覆盖集
    • 二分图的最大匹配——匈牙利算法
    • 二分图的最佳匹配算法——KM算法
    • 一般图的匹配

  4. 动态规划

    • 复杂动态规划模型构建
    • 复杂动态规划模型的优化

数学

数学

  1. 信息论基础

    • 熵、互信息、条件熵、相对熵的基本概念
    • 信息复杂度的基本概念
    • 描述复杂度的基本概念
    • 通讯复杂度的基本概念

  2. 初等数论

    • 原根和指数
    • 大步小步（`Baby Step Giant Step, BSGS）算法
    • 完全数
    • 狄利克雷（Dirichlet）卷积
    • 平方剩余
    • 二次同余式
    • 二次互反律

  3. 离散数学

    • 代数系统的基本概念
    • 群的基本概念
    • 置换群与循环群

  4. 组合数学

    • 母函数
    • 莫比乌斯变换
    • Burnside引理与Polya原理
    • 斯特林数

  5. 高等数学

    • 多项式函数微分
    • 多项式函数积分
    • 泰勒级数
    • 快速傅里叶变换（Fast Fourier Transform, FFT）
    • 卷积

  6. 线性代数

    • 矩阵的逆运算
    • 行列式及其运算
    • 线性相关与矩阵的逆

  7. 概率论

    • 概率相关概念
    • 求概率的乘法公式、全概率公式、贝叶斯公式

  8. 博弈论

    • 零和博弈问题——Nim博弈等
    • Sprague-Garundy(SG)函数概念及应用

  9. 运筹学

    • 线性规划之单纯形法

  10. 计算几何

    • 矢量及其运算
    • 点、线、面之间的位置判断
    • 常见图形的面积计算
    • 二维凸包的求法及其应用
    • 半平面交
最后更新: 2021-09-16
Back to top