数学类问题

  1. 精度处理(高精度、实数处理、各种浮点类型处理方法)
  2. 组合数学问题(斐波那契数列、第二类数、卡特兰数、Polya原理、排列组合计数、加法原理与乘法原理)
  3. 进制问题(特定二进制串的统计、二分查找、利用二进制进行路径、状态描述、二进制转换)
  4. 递推与递归关系(递推关系式、通项公式、数列、博弈问题)
  5. 数位、数字、特定数值的查找、统计(数值处理、质因子分解、幂次分解、数值表达式、添加运算符、分式与实数运算)
  6. 数学杂题(回文数字、矩阵处理、约瑟夫与反约瑟夫问题)
  7. 数学剪枝(无解判定、解线性方程组、限定搜索范围)

常用策略

  1. 相关公式、定理、原理的应用
  2. 寻找规律、归纳整理递归与递推关系式
  3. 按照数学方法构造、二进制转化等技巧性处理
  4. 注意事项:
    A. 规律准确(小数据手工推算、搜索程序验证)
    B. 数据类型是否合理、数据范围是否超界(大数据处理)

字符、字串类问题

  1. 读入、分离和统计问题(文件结束符、行结束符、空格符、回车符、字符组合分离、统计)
  2. 插入、删除、修改、替换等相关编辑问题(字符距离、优美编辑、初始状态与目标状态的变换、迭代等处理性问题)
  3. KMP算法及其改正
  4. 回文串、高精度运算及其以字符(串)作为处理对象的相关问题

常用策略

  1. 一般性字符处理
  2. 动态规划方法
  3. 字符树(查找、树的前序、中序、后序遍历)
  4. 注意事项:
    A. 读入时小心
    B. 字符串类型与字符数组存贮及其压缩存取

统计类问题

  1. 方案总数统计(矩阵、三角形划分方案统计、问题解集个数统计)
  2. 特定、离散元素统计(二进制统计问题)
  3. 横向、纵向规模化问题(数据范围、数据维数巨大)
  4. 离散化问题(卫星覆盖、图形周长)
  5. 一般性统计问题(时间复杂度)

常用策略

  1. 扫描技术、归类统计及平面、空间坐标体系变换等几何学知识
  2. 离散化思想
  3. 线段树处理方法
  4. 降维、剪枝
  5. 借助于数学方法进行统计
  6. 注意事项:
    A. 统计计数:避免待统计元素的遗漏、重复
    B. 多次读文件、边读边处理等大数据文件的处理技巧

模拟类问题

  1. 按题设描述进行直接模拟
  2. 队列模型模拟
  3. 按时间顺序模拟状态

常用策略

  1. 按条件描述直接模拟
  2. 注意事件发生的起止时间、状态的变化
  3. 按某一指标(时间)排序进行预处理
  4. 注意事项:
    A. 准确理解题意,切忌加入个人想当然思想,严格按题意进行模拟
    B. 一般来说要考虑的因素较多,做题前要有绝对清晰的思路并逐步修正要考虑的各种因素

搜索类问题

  1. 枚举类问题(有较好枚举方法或枚举量不大的问题)
  2. 产生式系统(产生式规则,生成新的元素类问题)
  3. 无任何好的解决办法或其他方法不能完成的问题
  4. 搜索与其他方法的结合(与动态规划的结合、与贪心思想的结合等)

常用策略

  1. 确定搜索对象和搜索策略
  2. 选取适合的搜索方法(深度、广度、记忆化搜索)
  3. 注意与其他方法的结合(贪心回溯、动态规划)
  4. 减少搜索量(剪枝)
  5. 注意事项:
    A. 剪枝条件的正确性(加剪枝条件与不加剪条件的程序结果对照)
    B. 搜索也是解决问题的一种方法,有时搜索程序也可以收到较好的效果,只要有较好的优化措施

最优化问题

  1. 图论中的最优化问题
  2. 规划问题
  3. 特定指标(长度、次数等)最(极)值问题

常用策略

  1. 动态规划
  2. 图论中经典算法及其改正
  3. 贪心+搜索解决办法
  4. 贪心思想
  5. 数学方法
  6. 注意事项:
    A. 动态规划阶段划分、状态描述及转移方程对动态规划效率的影响
    B. 状态存贮对空间优化的影响(根据题目特点决定状态存贮数目、状态存贮方法的选取(滚动存贮、压缩存贮))
    C. 双层动态规划
    D. 多次动态规划

图论问题

  1. 最小生成树问题、最小点基、中心点设置
  2. 路径问题(最短路、关键路径、道路、ERLUR回路、哈密顿回路)
  3. 拓扑排序问题(顶点的度)
  4. 连通性问题(添加、删除边、点增加或减少连通度)
  5. 流量问题
  6. 二部图的匹配问题(最大匹配、最佳匹配)

常用策略

  1. 点、边、权、度等图中基本元素关系
  2. 拓朴排序作预处理
  3. 图论算法的变形与改正
  4. 图搜索算法
  5. 标号法
  6. 动态规划方法
  7. 注意事项:
    A. 选取图结构的存贮数据结构(矩阵、邻接表)
    B. 在构建图模型时,考虑是否有多种构图方法

NOIP (CSP-J/S) 历年题目合集(2008-2019)

自2019年起,NOIP已不再设立提高组和普及组,2019年及其以后的题目均来自CSP-J/S

提高组

NOIP 提高组在 2010 年及以前为一试四题,2011 年及以后为两试共六题。

2008

编号 题号 题目名
T1 P1125 笨小猴
T2 P1149 火柴棒等式
T3 P1006 传纸条
T4 P1155 双栈排序

2009

编号 题号 题目名
T1 P1071 潜伏者
T2 P1072 Hankson 的趣味题
T3 P1073 最优贸易
T4 P1074 靶形数独

2010

编号 题号 题目名
T1 P1540 机器翻译
T2 P1541 乌龟棋
T3 P1525 关押罪犯
T4 P1514 引水入城

2011

编号 题号 题目名
D1T1 P1003 铺地毯
D1T2 P1311 选择客栈
D1T3 P1312 Mayan 游戏
D2T1 P1313 计算系数
D2T2 P1314 聪明的质监员
D2T3 P1315 观光公交

2012

编号 题号 题目名
D1T1 P1079 Vigenère 密码
D1T2 P1080 国王游戏
D1T3 P1081 开车旅行
D2T1 P1082 同余方程
D2T2 P1083 借教室
D2T3 P1084 疫情控制

2013

注:D2T1 与 NOIP 2018 提高组 D1T1 完全一致。

编号 题号 题目名
D1T1 P1965 转圈游戏
D1T2 P1966 火柴排队
D1T3 P1967 货车运输
D2T1* P1969 积木大赛
D2T2 P1970 花匠
D2T3 P1979 华容道

2014

编号 题号 题目名
D1T1 P1328 生活大爆炸版石头剪刀布
D1T2 P1351 联合权值
D1T3 P1941 飞扬的小鸟
D2T1 P2038 无线网络发射器选址
D2T2 P2296 寻找道路
D2T3 P2312 解方程

2015

编号 题号 题目名
D1T1 P2615 神奇的幻方
D1T2 P2661 信息传递
D1T3 P2668 斗地主
D2T1 P2678 跳石头
D2T2 P2679 子串
D2T3 P2680 运输计划

2016

编号 题号 题目名
D1T1 P1563 玩具谜题
D1T2 P1600 天天爱跑步
D1T3 P1850 换教室
D2T1 P2822 组合数问题
D2T2 P2827 蚯蚓
D2T3 P2831 愤怒的小鸟

2017

编号 题号 题目名
D1T1 P3951 小凯的疑惑
D1T2 P3952 时间复杂度
D1T3 P3953 逛公园
D2T1 P3958 奶酪
D2T2 P3959 宝藏
D2T3 P3960 列队

2018

注:D1T1 与 NOIP 2013 提高组 D2T1 完全一致。

编号 题号 题目名
D1T1* P5019 铺设道路
D1T2 P5020 货币系统
D1T3 P5021 赛道修建
D2T1 P5022 旅行
D2T2 P5023 填数游戏
D2T3 P5024 保卫王国

2019

即 2019 年非专业级软件能力认证第二轮提高级(CSP-S2)。

编号 题号 题目名
D1T1 P5657 格雷码
D1T2 P5658 括号树
D1T3 P5659 树上的树
D2T1 P5664 Emiya 家今天的饭
D2T2 P5665 划分
D2T3 P5666 树的重心

普及组

NOIP 普及组为一试四题。

2008

编号 题号 题目名
T1 P1055 ISBN 号码
T2 P1056 排座椅
T3 P1057 传球游戏
T4 P1058 立体图

2009

编号 题号 题目名
T1 P1067 多项式输出
T2 P1068 分数线划定
T3 P1069 细胞分裂
T4 P1070 道路游戏

2010

编号 题号 题目名
T1 P1179 数字统计
T2 P1190 接水问题
T3 P1158 导弹拦截
T4 P1199 三国游戏

2011

编号 题号 题目名
T1 P1307 数字反转
T2 P1308 统计单词数
T3 P1309 瑞士轮
T4 P1310 表达式的值

2012

注:T4 后被证明为错题。不存在一个算法能通过题目数据范围内的所有合法数据。

编号 题号 题目名
T1 P1075 质因数分解
T2 P1076 寻宝
T3 P1077 摆花
T4* P1078 文化之旅

2013

编号 题号 题目名
T1 P1980 计数问题
T2 P1981 表达式求值
T3 P1982 小朋友的数字
T4 P1983 车站分级

2014

编号 题号 题目名
T1 P2118 比例简化
T2 P2141 珠心算测验
T3 P2239 螺旋矩阵
T4 P2258 子矩阵

2015

编号 题号 题目名
T1 P2669 金币
T2 P2670 扫雷游戏
T3 P2671 求和
T4 P2672 推销员

2016

编号 题号 题目名
T1 P1909 买铅笔
T2 P2010 回文日期
T3 P2058 海港
T4 P2119 魔法阵

2017

编号 题号 题目名
T1 P3954 成绩
T2 P3955 图书管理员
T3 P3956 棋盘
T4 P3957 跳房子

2018

编号 题号 题目名
T1 P5015 标题统计
T2 P5016 龙虎斗
T3 P5017 摆渡车
T4 P5018 对称二叉树

2019

即 2019 年非专业级软件能力认证第二轮入门级(CSP-J2)。

编号 题号 题目名
T1 P5660 数字游戏
T2 P5661 公交换乘
T3 P5662 纪念品
T4 P5663 加工零件