问题类型与知识点范围

下表是不同比赛中经常出现的问题类型，可以理解成大体的考纲(Syllabus)。

CSP-J

来自图爸编程

C++程序设计: 见基本环境、技能与编程语言

数据结构

项目内容
线性表链表：单链表、双向链表、循环链表；栈；队列
简单树树的定义及其相关概念；树的父亲表示法；二叉树的定义及其基本性质；二叉树的孩子表示法；二叉树的遍历：前序、中序、后序遍历
特殊树完全二叉树的定义与基本性质；完全二叉树的数组表示法；哈夫曼树的定义、构造及其遍历；二叉树的定义、构造及其遍历
简单图图的定义及其相关概念；图的邻接矩阵存储；图的邻接表存储

算法

项目内容
入门枚举法；模拟法
基础贪心法；递推法；递归法；二分法；倍增法
数值处理（高精度计算）高精度的加法；高精度的减法；高精度的乘法；求高精度整数除以单精度整数的商和余数
排序排序的基本概念（稳定性等）；冒泡排序；简单选择排序；简单插入排序
图论图的深度优先遍历算法；图的宽度优先遍历算法；洪水填充算法（floodfill）
动态规则动态规划的基本思路；简单一维动态规划；简单背包类型动态规划；简单区间类型动态规划

数学知识

项目内容
基础数论奇偶、整除、同余、斐波那契数列、素数定理及其判定、埃氏筛法、线性筛、GCD、LCM、快速幂
基础计数集合的计算、计数原理、排列组合、容斥原理、鸽巢原理
概率与统计事件频率、概率、数据图表（直方图）
平面几何平面直角坐标系、点、直线、多边形、矢量的概念及简单运算
矩阵矩阵的表示形式、矩阵基本运算
初等代数函数的定义与性质、基本初等函数、分段函数、对数函数、函数的零点、函数和图的关系、函数区间内单调性、不等式
数列数列的概念、特殊数列、等比等差数列概念和性质，数列的递推、常用数列通项公式、求和公式

CSP-S / NOIP

CSP-S和NOIP首先包含上面的CSP-J知识范围，以及以下内容（来自知乎）：

  1. 较难的动态规划：多维的状态，转移方式较多。
  2. 简单数论：如扩展GCD，欧拉函数等。
  3. 进阶算法：倍增，并查集，差分约束、拓扑排序，排列组合数，逆元，哈希。
  4. 最短路问题：需要掌握弗洛伊德算法、SPFA算法、Dijkstra算法，以及它们对应的优化，再根据题目实际要求进行变形，用同样模板达到各种不一样的效果。
  5. 最小生成树问题：主要的两种算法为Prim和Kruskal，同样要加上对应的优化，再根据题目进行变形，以满足题目的实际要求。
  6. 二分图染色、二分图匹配，一般题目都隐藏得很深，需要找到题目的本质，才能发现正确的解法。
  7. 强连通分量Tarjan，最近公共祖先LCA。
  8. 数据结构：线段树、字典树、主席树、树状数组等。
  9. 树的更多操作：树链剖分、树的直径、树的重心等。
  10. 字符串算法：KMP等。

省赛和NOI

同样来自知乎

  1. 搜索：启发式搜索（A*）、迭代加深、IDA*、随机化搜索
  2. 图论：网络流、仙人掌算法
  3. 树：平衡树、树套树、圆方树、线段树合并
  4. 数学：容斥原理、莫比乌斯反演、中国剩余定理、欧拉定理、矩阵乘法、FFT、博弈论相关、计算几何
  5. 字符串：字符串哈希、AC自动机、后缀数组、后缀自动机、回文自动机、manacher

USACO Silver/Gold