问题类型与知识点范围

下表是不同比赛中经常出现的问题类型，可以理解成大体的考纲(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

• USACO Silver没有DP，字符串算法、强连通分量。
• USACO Gold可以认为与CSP-S/NOIP知识范围一致。
• 总体出题风格上，USACO题目比较灵活，USACO Silver虽然知识点范围较小，但对思维能力要求还是比较高的。
• 正因为题目较灵活，套路化较低，而且每年3场比赛，所以USACO题库是非常好的练习用题目。