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

NOIP普及组历届试题分析NOIP普及组题型分布题型题目枚举扫雷游戏(2015p2)、珠心算测验(2014p1)数字统计(2010p1)、比例简化(2014p2)模拟金币(2015p1)、螺旋方阵(2014p3)、计数问题(2013p1)、字符串数字反转(2011p1)、统计单词个数(2011p2)贪心NOIP普及组题型分布题型题目简单动态规划子矩阵(2014p4)、小朋友的数字(2013p3)数学/数论数据结构表达式求值(2013p2)、图论（提高组）车站分级(2013p4拓扑排序)一、枚举类试题枚举法的基本思想是根据提出的问题枚举所有可能的解，并用问题给定的条件检验哪些解是需要的，哪些解是不需要的。能使条件成立，即为其解。枚举法其实是最简单的搜索算法。珠心算测验(noip2014普及组第一题)珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？最近老师出了一些测验题，请你帮忙求出答案。珠心算测验(noip2014普及组第一题)【输入】输入共两行，第一行包含一个整数n，表示测试题中给出的正整数个数。第二行有n个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。【输出】输出共一行，包含一个整数，表示测验题答案。【样例输入】【样例输出】421234对于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出现的次数。样例输入：222样例输出：6扫雷游戏(noip2015普及组第二题)扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。扫雷游戏(noip2015普及组第二题)输入样例133*??????*?输入样例223?*?*??输出样例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，请你将A比B化简为A’比B’，要求在A’和B’均不大于L且A’和B’互质（两个整数的最大公约数是1）的前提下，A’/B’≥A/B且A’/B’-A/B的值尽可能小。比例简化(noip2014普及组第二题)输入格式输入共一行，包含三个整数A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。输出格式输出共一行，包含两个整数A’，B’，中间用一个空格隔开，表示化简后的比例。样例输入149890210样例输出53二、模拟类试题有些问题，我们很难建立数学模型，或者很难用计算机建立递推、递归、枚举、回溯法等算法。在这种情况下，一般采用模拟策略。所谓模拟策略就是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。金币(noip2015普及组第一题)国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1天里，每天收到N+1枚金币。请计算在前K天里，骑士一共获得了多少金币。输入格式：输入文件只有1行，包含一个正整数K，表示发放金币的天数。输出格式：输出文件只有1行，包含一个正整数，即骑士收到的金币数。输入输出样例输入样例：1000输出样例：29820螺旋方阵(noip2014普及组第三题)一个n行n列的螺旋矩阵可由如下方法生成：从矩阵的左上角(第1行第1列)出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入1,2,3,....，便构成了一个螺旋矩阵。现给出矩阵大小n以及i和j，请你求出该矩阵中第i行第j列的数是多少。下图是一个n=4时的螺旋矩阵。螺旋方阵(noip2014普及组第三题)输入格式输入共一行，包含三个整数n，i，j，每两个整数之间用一个空格隔开，分别表示矩阵大小、待求的数所在的行号和列号。输出格式输出共一行，包含一个整数，表示相应矩阵中第i行第j列的数。样例输入：423样例输出：14对于50%的数据，1≤n≤100;对于100%的数据，1≤n≤30,000，1≤i≤n，1≤j≤n。螺旋方阵试题分析本题首先让我们想到传统的模拟，从[1,1]开始往数组中填充数字，但对于[30000,30000]的数组，直接爆零。对于读入的n,x,y，先判断(x,y)在第几圈，再模拟圈内的数字。螺旋方阵试题分析如：n=4,(2,2)在第2圈，(3,1)在第1圈。n=6，(4,5)在第2圈螺旋方阵试题分析目标位置(i,j)到底在当前这一圈的第几个位置？如目标数26所在的位置(4,5)，在第2圈的什么位置？分两种情况：1）目标数(i,j)在上行或右行；i+j-2q+12）目标数(i,j)在下行或左行；距离第一个数的距离i+j-2q+1计数问题(noip2013普及组第一题)试计算在区间1到n的所有整数中，数字x（0≤x≤9）共出现了多少次？例如，在1到11中，即在1、2、3、4、5、6、7、8、9、10、11中，数字1出现了4次。输入：输入共1行，包含2个整数n、x，之间用一个空格隔开。输出：输出共1行，包含一个整数，表示x出现的次数。输入示例：111输出示例：4其他说明：对于100%的数据，1≤n≤1,000,000，0≤x≤9。三、字符串类试题对于字符串、表达式的求解、大整数的处理等等，我们经常采用字符串来处理。字符串处理常见函数：数字反转(noip2011普及组第一题)给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（如：输入-380，输出-83）。输入输入共1行，一个整数N。输出输出共1行，一个整数，表示反转后的新数。样例输入123样例输出321统计单词个数(noip2011普及组第二题)一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。统计单词个数(noip2011普及组第二题)输入格式第1行为一个字符串，其中只含字母，表示给定单词；第2行为一个字符串，其中只可能包含字母和空格，表示给定的文章。输出格式只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从0开始）；如果单词在文章中没有出现，则直接输出一个整数-1。统计单词个数(noip2011普及组第二题)样例输入1：Totobeornottobeisaquestion样例输出1：20样例输入2：toDidtheOttomanEmpireloseitspoweratthattime样例输出2：-1【输入输出样例2说明】表示给定的单词to在文章中没有出现，输出整数-1。注释说明1≤单词长度≤10。1≤文章长度≤1,000,000。六、简单动态规划类试题动态规划是解决多阶段决策最优化问题的一种思想方法。一般我们从初始阶段出发，枚举每个阶段的所有状态，在状态转移的过程中，我们需要决策。根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。普及组一般考查的动态规划：01背包，最长上升子序列，一些简单的线性动规。采药（noip2005普及组第三题）辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”采药（noip2005普及组第三题）输入格式：第一行有两个整数T和M，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。输出格式：一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。输入样例：7037110069112输出样例：3（1=T=1000）（1=M=100）采药（noip2005普及组第三题）题目大意：共m株草药，每株草药有一个价值和采摘的时间，问t时间能采摘到的草药的最大价值。01背包。把时间看成背包的重量，题目就变成了重量为t的背包能装的最大价值。采药（noip2005普及组第三题）dp[j]表示采前i株草药获得的最大价值。对于第i株草药，我们可以采摘，也可以不采。如果不采：dp[i]不变如果采：那么前i-1株草药花费的时间j-w[i]元，价值变成dp[j-w[i]]+v[i];dp[i]=max(dp[i],dp[j-w[i]]+v[i]);七、数学/数论类试题信息学竞赛中经常涉及一些数学及数论知识。常见的有数的各位和、质因数分解、最大公约数和最小公倍数、排列与组合等等。八、数据结构普及组中，数据结构常考的有栈和队列、树与二叉树、树的遍历。图一般不作要求，但也有涉及。如20