信息学奥赛NOIP普及组历届试题分析.ppt

七、数学/数论类试题 信息学竞赛中经常涉及一些数学及数论知识。常见的有数的各位和、质因数分解、最大公约数和最小公倍数、排列与组合等等。 八、数据结构 普及组中，数据结构常考的有栈和队列、树与二叉树、树的遍历。图一般不作要求，但也有涉及。如2012年普及组第4题《文化之旅》，就是一个裸的floyd算法。 NOIP普及组历届试题分析 NOIP普及组题型分布 题型 题目 枚举 扫雷游戏(2015p2)、珠心算测验(2014p1) 数字统计(2010p1)、比例简化(2014p2) 模拟 金币(2015p1)、 螺旋方阵(2014p3)、计数问题(2013p1)、 字符串 数字反转(2011p1)、统计单词个数(2011p2) 贪心 NOIP普及组题型分布 题型 题目 简单 动态规划 子矩阵(2014p4)、小朋友的数字(2013p3) 数学/数论 数据结构 表达式求值(2013p2)、 图论（提高组） 车站分级(2013p4 拓扑排序) 一、枚举类试题 枚举法的基本思想是根据提出的问题枚举所有可能的解，并用问题给定的条件检验哪些解是需要的，哪些解是不需要的。能使条件成立，即为其解。 枚举法其实是最简单的有哪些信誉好的足球投注网站算法。 珠心算测验 (noip2014普及组第一题) 珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。 某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？ 最近老师出了一些测验题，请你帮忙求出答案。 珠心算测验 (noip2014普及组第一题) 【输入】 输入共两行，第一行包含一个整数n，表示测试题中给出的正整数个数。 第二行有n个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。 【输出】 输出共一行，包含一个整数，表示测验题答案。 【样例输入】 【样例输出】 4 2 1 2 3 4 对于100%的数据，3?≤?n?≤?100 测验题给出的正整数大小不超过10,000。 试题分析 题意大意：给你n个数，在这n个数中，找到满足A+B=C的个数，注意不是这个等式的个数。 样例中，1,2,3,4有1+2=3，1+3=4两个。 由于本题数据规模n=100，我们可以直接枚举C, A, B，三层循环解决问题。 数字统计 (noip2010普及组第一题) 请统计某个给定范围[L, R]的所有整数中，数字2出现的次数。 比如在给定范围[2, 22]，数字2在数2中出现了1次，在数12中出现了1次，在数20中出现了1次，在数21中出现了1次，在数22中出现了2次，所以数字2在该范围内一共出现了6次。 输入格式 输入共一行，为两个正整数L和R，之间用一个空格隔开。 输出格式 输出共1行，表示数字2出现的次数。 样例输入：2 22 样例输出：6 扫雷游戏 (noip2015普及组第二题) 扫雷游戏是一款十分经典的单机小游戏。 在 n 行 m 列的雷区中有一些格子含有地雷（称之为地雷格） ，其他格子不含地雷（称之为非地雷格） 。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。 游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。 现在给出n行m列的雷区中的地雷分布， 要求计算出每个非地雷格周围的地雷格数。注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。 扫雷游戏 (noip2015普及组第二题) 输入样例?13?3*??????*? 输入样例?22?3?*?*?? 输出样例?1mine.out*102211*1 输出样例?2mine.out2*1*21 对于?100%的数据，1≤n≤100，1≤m≤100 比例简化 (noip2014普及组第二题) 在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某 一观点表示支持的有 1498 人，反对的有 902 人，那么赞同与反对的比例可以简单的记为1498:902。 不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 5:3，虽然与 真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。 现给出支持人数 A，反对人数 B，以及一个上限 L，请你将