单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,最新.,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,最新.,*,NOIP,普及组历届试题分析,最新.,1,NOIP普及组历届试题分析最新.1,NOIP,普及组题型分布,最新.,2,NOIP普及组题型分布最新.2,NOIP,普及组题型分布,最新.,3,NOIP普及组题型分布最新.3,一、枚举类试题,枚举法的基本思想是根据提出的问题枚举所有可能的解，并用问题给定的条件检验哪些解是需要的，哪些解是不需要的。能使条件成立，即为其解。,枚举法其实是最简单的搜索算法。,最新.,4,一、枚举类试题枚举法的基本思想是根据提出的问题枚举所有可能的,珠心算测验,(noip2014,普及组第一题,),珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。,某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？最近老师出了一些测验题，请你帮忙求出答案。,最新.,5,珠心算测验(noip2014普及组第一题)珠心算是一种通过,珠心算测验,(noip2014,普及组第一题,),【,输入,】,输入共两行，第一行包含一个整数,n,，表示测试题中给出的正整数个数。,第二行有,n,个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。,【,输出,】,输出共一行，包含一个整数，表示测验题答案。,【,样例输入,】【,样例输出,】,4 2,1 2 3 4,对于,100%,的数据，,3n100,测验题给出的正整数大小不超过,10,000,。,最新.,6,珠心算测验(noip2014普及组第一题)【输入】对于1,试题分析,题意大意：给你,n,个数，在这,n,个数中，找到满足,A+B=C,的个数，,注意不是这个等式的个数,。,样例中，,1,2,3,4,有,1+2=3,，,1+3=4,两个。,由于本题数据规模,n=100,，我们可以直接,枚举,C,A,B,，三层循环解决问题。,最新.,7,试题分析题意大意：给你n个数，在这n个数中，找到满足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,最新.,8,数字统计(noip2010普及组第一题)请统计某个,扫雷游戏,(noip2015,普及组第二题,),扫雷游戏是一款十分经典的单机小游戏。在,n,行,m,列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字,提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。现在给出,n,行,m,列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。,最新.,9,扫雷游戏(noip2015普及组第二题),扫雷游戏,(noip2015,普及组第二题,),输入样例,133*?*?,输入样例,223?*?*?,输出样例,1mine.out*102211*1,输出样例,2mine.out2*1*21,对于,100%,的数据，,1n100,，,1m100,最新.,10,扫雷游戏(noip2015普及组第二题)输入样例1,比例简化,(noip2014,普及组第二题,),在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某 一观点表示支持的有,1498,人，反对的有,902,人，那么赞同与反对的比例可以简单的记为,1498:902,。,不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为,5:3,，虽然与 真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。,现给出支持人数,A,，反对人数,B,，以及一个上限,L,，请你将,A,比,B,化简为,A,比,B,，要求在,A,和,B,均不大于,L,且,A,和,B,互质（两个整数的最大公约数是,1,）的前提下，,A/B A/B,且,A/B-A/B,的值尽可能小。,最新.,11,比例简化(noip2014普及组第二题)在社交媒体上，经常,比例简化,(noip2014,普及组第二题,),输入格式,输入共一行，包含三个整数,A,，,B,，,L,，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。,输出格式,输出共一行，包含两个整数,A,，,B,，中间用一个空格隔开，表示化简后的比例。,样例输入,1498 902 10,样例输出,5 3,最新.,12,比例简化(noip2014普及组第二题)输入格式最新.12,二、模拟类试题,有些问题，我们很难建立数学模型，或者很难用计算机建立递推、递归、枚举、回溯法等算法。在这种情况下，一般采用模拟策略。,所谓模拟策略就是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。,最新.,13,二、模拟类试题有些问题，我们很难建立数学模型，或者很难用计算,金币,(noip2015,普及组第一题,),国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币,；这种工资发放模式会一直这样延续下去：当连续,N,天每天收到,N,枚金币后，骑士会在之后的连续,N+1,天里，每天收到,N+1,枚金币。请计算在前,K,天里，骑士一共获得了多少金币。,输入格式：输入文件只有,1,行，包含一个正整数,K,，表示发放金币的天数。,输出格式：输出文件只有,1,行，包含一个正整数，即骑士收到的金币数。,输入输出样例,输入样例：,1000,输出样例：,29820,最新.,14,金币(noip2015普及组第一题)国王将金币作为工资，发,螺旋方阵,(noip2014,普及组第三题,),一个,n,行,n,列的螺旋矩阵可由如下方法生成：,从矩阵的左上角,(,第,1,行第,1,列,),出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入,1,2,3,.,，便构成了一个螺旋矩阵。,现给出矩阵大小,n,以及,i,和,j,，请你求出该矩阵中第,i,行第,j,列的数是多少。,下图是一个,n=4,时的螺旋矩阵。,最新.,15,螺旋方阵(noip2014普及组第三题)一个n行n列的螺旋,螺旋方阵,(noip2014,普及组第三题,),输入格式,输入共一行，包含三个整数,n,，,i,，,j,，每两个整数之间用一个空格隔开，分别表示矩阵大小、待求的数所在的行号和列号。,输出格式,输出共一行，包含一个整数，表示相应矩阵中第,i,行第,j,列的数。,样例输入：,4 2 3,样例输出：,14,对于,50%,的数据，,1 n 100;,对于,100%,的数据，,1 n 30,000,，,1 i n,，,1 j n,。,最新.,16,螺旋方阵(noip2014普及组第三题)输入格式最新.16,螺旋方阵试题分析,本题首先让我们想到传统的模拟，从,1,1,开始往数组中填充数字，但对于,30000,30000,的数组，直接爆零。,对于读入的,n,x,y,，先判断,(x,y),在第几圈，再模拟圈内的数字。,最新.,17,螺旋方阵试题分析本题首先让我们想到传统的模拟，从1,1开,螺旋方阵试题分析,如：,n=4,(2,2),在第,2,圈，,(3,1),在第,1,圈。,n=6,，,(4,5),在第,2,圈,最新.,18,螺旋方阵试题分析如：n=4,(2,2)在第2圈，(3,1),螺旋方阵试题分析,目标位置,(i,j),到底在当前这一圈的第几个位置？,如目标数,26,所在的位置,(4,5),，在第,2,圈的什么位置？,分两种情况：,1,）目标数,(i,j),在上行或右行；,i+j-2q+1,2,）目标数,(i,j),在下行或左行；,距离第一个数的距离,i+j-2q+1,最新.,19,螺旋方阵试题分析目标位置(i,j)到底在当前这一圈的第几个位,计数问题,(noip2013,普及组第一题,),试计算在区间,1,到,n,的所有整数中，数字,x,（,0 x9,）共出现了多少次？例如，在,1,到,11,中，即在,1,、,2,、,3,、,4,、,5,、,6,、,7,、,8,、,9,、,10,、,11,中，数字,1,出现了,4,次。,输入：,输入共,1,行，包含,2,个整数,n,、,x,，之间用一个空格隔开。,输出：,输出共,1,行，包含一个整数，表示,x,出现的次数。,输入示例：,111,输出示例：,4,其他说明：,对于,100%,的数据，,1n1,000,000,，,0 x9,。,最新.,20,计数问题(noip2013普及组第一题)试计算在区间1到n,三、字符串类试题,对于字符串、表达式的求解、大整数的处理等等，我们经常采用字符串来处理。,字符串处理常见函数：,最新.,21,三、字符串类试题对于字符串、表达式的求解、大整数的处理等等,数字反转,(noip2011,普及组第一题,),给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（如：输入,-380,，输出,-83,）。,输入,输入共,1,行，一个整数,N,。,输出,输出共,1,行，一个整数，表示反转后的新数。,样例输入,123,样例输出,321,最新.,22,数字反转(noip2011普及组第一题)给定一个整数，请将,统计单词个数,(noip2011,普及组第二题,),一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例,1,），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例,2,）。,最新.,23,统计单词个数(noip2011普及组第二题)一般的文本编辑,统计单词个数,(noip2011,普及组第二题,),输入格式,第,1,行为一个字符串，其中只含字母，表示给定单词；第,2,行为一个字符串，其中只可能包含字母和空格，表示给定的文章。,输出格式,只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从,0,开始）；如果单词在文章中没有出现，则直接输出一个整数,-1,。,最新.,24,统计单词个数(noip2011普及组第二题)输入格式最新.,统计单词个数,(noip2011,普及组第二题,),样例输入,1,：,Totobeornottobeisaquestion,样例输出,1,：,