• 首页
  • 教育理念
  • 文章专题
  • 编程教程
    • – Scratch编程教程
    • – AppInventor编程
    • – Python编程教程
    • – NOIP信息学奥赛
    • – C/C++编程教程
    • – JS编程教程
  • 少儿编程学院
    • – 在线课程
    • – 学院名师
    • – 动态资讯
  • 少儿编程社区
    • – 在线编程
    • – 编程作品
    • – 专题创作
  • 更多
    • – APP客户端
    • – 关于我们
    • – 寻求合作
    • – 少儿编程联盟
投稿 登录 注册
  • 首页
  • 文章专题
  • 教育理念
  • 编程教程
  • 少儿编程学院
  • 微信公众号
  • APP客户端
少儿编程学院
少儿编程教育-微信公众号
首页 › 编程教程 › NOIP信息学奥赛 › 正文
NOIP信息学奥赛信息竞赛编程竞赛

NOIP复赛复习(一)常见问题与常用策略

主编主编 NOIP信息学奥赛 2017-09-18 2,359 0

数学类问题
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. 在构建图模型时,考虑是否有多种构图方法


2000-2016年NOIP普及组与提高组复赛考察内容

 

NOIP复赛复习(一)常见问题与常用策略-少儿编程教育网
喜欢 (0)
打赏
  • 打赏支付宝扫一扫
  • 打赏微信扫一扫
微博 微信 QQ

微信扫一扫,分享到朋友圈

微信公众号
编程少年Scratch实物积木
少儿编程教育-微信公众号
上一篇

少儿编程教育网受邀参加2017全国双创周,精彩回顾!

下一篇

15岁少年自学编程,为老年痴呆症的爷爷做出最温暖发明!

猜你喜欢

  • 第二届全国中学生网络安全竞赛即将在西安电子科大举办!

    第二届全国中学生网络安全竞赛即将在西安电子科大举办!

  • 严查违规竞赛,29项全国中小学生竞赛活动名单公布!

    严查违规竞赛,29项全国中小学生竞赛活动名单公布!

  • 教育部:2019年度中小学生全国性竞赛活动名单公示

    教育部:2019年度中小学生全国性竞赛活动名单公示

  • 第二十届全国中小学电脑制作活动通知

    第二十届全国中小学电脑制作活动通知

  • 2018年全国青少年创意编程大赛,终评活动即将开启!

    2018年全国青少年创意编程大赛,终评活动即将开启!

  • STEAM教育专题 | 源自硅谷的机器人教育机构萝卜太辣

    STEAM教育专题 | 源自硅谷的机器人教育机构萝卜太辣

主编
主编官方

我真的不是自黑!

中国STEAM教育2018年度风云榜

微信公众号

推荐专题

  • 有趣的少儿编程游戏推荐

    查看专题
  • 国外优秀的少儿编程教育

    查看专题
  • S科学-T技术-E工程-M数学

    查看专题

猜你喜欢

  • 儿童编程培训班多少钱?少儿编程培训班多少钱?
    2019-10-12

    儿童编程培训班多少钱?少儿编程培训班多少钱?

  • 2018年第十九届全国中小学电脑制作活动开赛啦!

    2018年第十九届全国中小学电脑制作活动开赛啦!

    2018-01-18
  • 2018年全国各高校自主招生对论文、专利的要求

    2018年全国各高校自主招生对论文、专利的要求

    2018-08-12
  • 啊哈C语言编程-第5课-多彩一点

    啊哈C语言编程-第5课-多彩一点

    2018-01-31
  • 真相!为什么他说人人都该从小开始学编程?

    真相!为什么他说人人都该从小开始学编程?

    2017-06-07

热门文章

    暂无文章

热门标签

鲨鱼公园高考改革高考加分青橙创客青少儿防疫阿部和广错误观念逻辑思维费米科学贝尔科教谷歌教育计算机科学计算机思维解决方案西瓜创客

微信公众号

热门文章 热门标签 年度归档 少儿编程教育联盟

Copyright © 2021 少儿编程教育网 粤ICP备17057575号 · Designed by shaoerbc.org

大家都在搜

  • Scratch教程
  • scratch2下载
  • Scratch编程
  • 编程思维
  • 信息学奥赛
  • STEM教育
  • 编程一小时
  • 自主招生
  • 少儿编程竞赛

关注我们的公众号

微信公众号