NOIP复赛试题类型归纳课件.ppt

1、数学类问题数学类问题 精度处理（高精度、实数处理、REAL类型处理方法）组合数学问题（Fibonacci数列、类数、卡特兰数、POLYA原理、排列组合计数、加法原理与乘法原理）进制问题（特定二进制串的统计、二分查找、利用二进制进行路径、状态描述、二进制转换）数学类问题数学类问题 递推与递归关系（递推关系式、通项公式、数列、博弈问题） 数位、数字、特定数值的查找、统计（数值处理、质因子分解、幂次分解、数值表达式、添加运算符、分式与实数运算） 数学杂题（回文数字、矩阵处理、约瑟夫与反约瑟夫问题） 数学剪枝（无解判定、解线性方程组、限定搜索范围）数学类问题的思维过程 相关公式、定理、原理的应用 寻找

2、规律、归纳整理递归与递推关系式 按照数学方法构造、二进制转化等技巧性处理 注意事项： 规律准确（小数据手工推算、搜索程序验证） 数据类型是否合理、数据范围是否超界（大数据处理）Kathy函数函数(function.exe) Tiger非常喜欢数学，所以他参加了学校组织的数学课外兴趣小组。在兴趣小组的学习当中，老师向Tiger介绍了Kathy函数，Kathy函数是这样定义的：)(2) 12(3)34()() 12(2) 14()()2(3)3(1) 1 (nfnfnfnfnfnfnfnfff Tiger对Kathy函数产生了浓厚的兴趣，他通过研究发现有很多的数n都满足。对于一个给定的数m，他希望

3、你求出所有的满足的自然数n的个数，其中。 输入输出要求 输入由文件”function.in”读入，仅有一行，为正整数m，。 输出到文件”function.out”，输出文件仅有一个正整数，表示所有的满足的自然数的个数。 输入输出样例 Function.inFunction.out53字符、字串处理类问题字符、字串处理类问题 读入、分离和统计问题（文件结束符、行结束符、空格符、回车符、字符组合分离、统计） 插入、删除、修改、替换等相关编辑问题（字符距离、优美编辑、初始状态与目标状态的变换、迭代等处理性问题） KMP算法及其改正 回文串、高精度运算及其以字符（串）作为处理对象的相关问题 一般性字符

4、处理 动态规划方法 字符树（查找、树的前序、中序、后序遍历） 注意事项： 读入时小心（READ、READLN语句及结束标记） 字符串类型与字符数组存贮及其压缩存取 表达式值的计算统计类问题统计类问题 方案总数统计（矩阵、三角形划分方案统计、问题解集个数统计） 特定、离散元素统计（01统计等二进制统计问题） 横向、纵向规模化问题（数据范围、数据维数巨大） 离散化问题 扫描技术、归类统计及平面、空间坐标体系变换等几何学知识 离散化思想 线段树处理方法 降维、剪枝 借助于数学方法进行统计 注意事项： 统计计数：避免待统计元素的遗漏、重复 多次读文件、边读边处理等大数据文件的处理技巧 求正整数N和M之

5、间具有最多真因子的数。本题中的真因子是这样定义的：如果RP而且R能整除P，我们就称R是P的真因子，对于特殊整数1，我们认为1是1的真因子。 参数范围：1NM999999999；M-N999999； 顺序查找法：依次统计规定范围内的各整数的真因子个数，记录最优解。 由于，分解质因数的算法时间复杂度为平方根级的，因此这个算法的时间复杂度为O(m-n)*m0.5)。（二）标号法：枚举不同的因数，标记它们的倍数。 分段统计法：将给定区间分成不重复且不遗漏的若干个子区间，然后按方法二统计。 由于方法一每次处理单一元素，因此时间耗费高，方法二将所有元素统一处理，因此空间需求大，而方法三则综合前两种方法的优

6、点，在充分利用空间的情况下，得到较高的时间效率。 方法三实质就是分解法的应用，由此我们将“分解法”定义如下： 以一定的算法为原型，将大规模的问题分解成若干个不遗漏且尽量不重复的相对独立的子问题，使得所有子问题解集的全集就是原问题的解集。模拟类问题模拟类问题 按题设描述进行直接模拟 队列模型模拟（银行事件驱动、公交车站、牙医诊所） 按时间（刻）顺序模拟状态（商船运输） 类Pascal语言程序（算法）运行模拟 按条件描述直接模拟 注意事件发生的起止时间、状态的变化 按某一指标（时间）排序进行预处理 注意事项： 准确理解题意，切忌加入个人想当然思想，严格按题意进行模拟 一般来说要考虑的因素较多，容易

7、让人思路糊涂，做题前要有绝对清晰的思路并逐步修正要考虑的各种因素搜索类问题搜索类问题 枚举类问题 产生式系统 无任何好的解决办法或其他方法不能完成的问题 搜索与其他方法的结合（与动态规划的结合、与贪心思想的结合等） 确定搜索对象和搜索策略 选取适合的搜索方法（深度、广度、记忆化搜索） 注意与其他方法的结合（贪心回朔、动态规划） 减少搜索量（剪枝） 注意事项： 剪枝条件的正确性（加剪枝条件与不加剪条件的程序结果对照） 搜索也是解决问题的一种方法，有时搜索程序也可以收到较好的效果，只要有较好的优化措施正方形剖分问题问题描述：将n n 个小格组成的大正方形分割成若干个较小的整数边长的正方形，要求分成

8、的小正方形数目最小。范围：1n32。编程环境：FreePascal。可用64MB空间n=7时的一个最小数目的剖分方案，需要9个小正方形。 分析当n为偶数时最少需要4个小正方形：1234n/2n/2n/2n/2当n为奇数时，很难发现有什么数学规律。0, 0)0()0(min,1000,jiNjijijkffikffNijijifkjikijkijkji或或设fi,j表示一个ij的矩形最少可以被剖分成多少个小正方形:n=7时，求出结果为10，并不是最优值。原因：最优方案不一定能被某条直线分割。ijkj-kijki-kn711131719232931其他fn,n1012121414161616相同最

9、优值911111313131415相差111113210fn,n仅是一个可行解，不过其值与最优解十分接近的。目前只能用搜索！优化：搜索之前先用上述动态规划方程求出一个较优值，限制搜索层次。 最优化问题图论中的最优化问题规划问题特定指标（长度、次数等）最（极）值问题 动态规划图论中经典算法及其改正贪心+搜索解决办法贪心思想数学方法图论问题图论问题 最小生成树问题 路径问题（最短路、关键路径、道路、回路（ERLUR回路、哈密顿回路） 拓扑排序问题（顶点的度） 连通性问题（添加、删除边、点增加或减少连通度） 流量问题 二部图的匹配问题（最大匹配、最佳匹配） 点、边、权、度等图中基本元素关系（骆驼商队问题） 拓朴排序作预处理 图论算法的变形与改正 图搜索算法 标号法 动态规划方法 注意事项： 选取图结构的存贮数据结构（矩阵、邻接表） 在构建图模型时，考虑是否有多种构图方法