问题类型与知识点范围

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