NOIP普及组历届试题分析

NOIP普及组历届试题分析引言noip复赛的知识面很广泛，对选手的综合素质考核要求更为严格，难度和分数的阶梯层次更趋科学合理，对信息学活动的推动力和社会公信力更为增强。NOIP普及组题型分布题型题目枚举扫雷游戏(2015p2)、珠心算测验(2014p1)数字统计(2010p1)、比例简化(2014p2)模拟金币(2015p1)、螺旋方阵(2014p3)、计数问题(2013p1)、寻宝(2012p2)、接水问题(2010p2)字符串数字反转(2011p1)、统计单词个数(2011p2)ISBN号码(2008p1)、乒乓球(2003p1)贪心排座椅(2008p2)、纪念品分组(2007p2)NOIP普及组题型分布题型题目简单动态规划子矩阵(2014p4)、小朋友的数字(2013p3)摆花(2012p3)、导弹拦截(2010p3)道路游戏(2009p4)、传球游戏(2008p3)守望者的逃离(2007p3)、开心的金明(2006p2)采药(2005p3)、数字游戏(2003p2)数学/数论质因数分解(2012p1)、细胞分裂(2009p3)Hanoi双塔问题(2007p4)、数列(2006p4)循环(2005p4)、栈(2003p3卡特兰数)数据结构表达式求值(2013p2)、表达式的值(2011p4)FBI树(2004p1)、求先序排列(2001p2)图论（提高组）车站分级(2013p4拓扑排序)文化之旅(2012p4floyd算法)一、枚举类试题枚举法的基本思想是根据提出的问题枚举所有可能的解，并用问题给定的条件检验哪些解是需要的，哪些解是不需要的。能使条件成立，即为其解。枚举法其实是最简单的搜索算法。珠心算测验(noip2014普及组第一题)珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？最近老师出了一些测验题，请你帮忙求出答案。珠心算测验(noip2014普及组第一题)【输入】输入共两行，第一行包含一个整数n，表示测试题中给出的正整数个数。第二行有n个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。【输出】输出共一行，包含一个整数，表示测验题答案。【样例输入】【样例输出】421234对于100%的数据，3≤n≤100测验题给出的正整数大小不超过10,000。试题分析题意大意：给你n个数，在这n个数中，找到满足A+B=C的C的个数，注意不是这个等式的个数。样例中，1,2,3,4有1+2=3，1+3=4两个。由于本题数据规模n=100，我们可以直接枚举C,A,B，三层循环解决问题。方法1：三层循环考试中，有许多选手的程序是这样的，错在哪里？ans:=0;forc:=1tondofora:=1tondoforb:=1tondoif(f[c]=f[a]+f[b])and(ca)and(ab)and(cb)theninc(ans);writeln(ans);样例中，上述错误答案是4：3=1+2,3=2+1,4=1+3,4=3+1方法1：参考程序1.vari,n,a,b,c,t,ans:longint;2.f:array[0..105]oflongint;3.begin4.readln(n);5.fori:=1tondoread(f[i]);6.ans:=0;7.forc:=1tondo8.begin9.t:=0;10.fora:=1tondo11.forb:=1tondo12.if(f[c]=f[a]+f[b])and(t=0)and(ca)and(ab)and(cb)then13.begin14.inc(ans);15.t:=1;16.end;17.end;18.writeln(ans);19.end.方法2：两层循环我们能不能使用两层循环呢？由于本题测验题给出的正整数大小不超过10,000，我们可以直接枚举A,B，判断A+B在不在给定的数中即可。定义一个数组vis，初始值为0；读入数a[i]时，vis[a[i]]标记为1。fori=1tondo{read(f[i]);vis[f[i]]=1;}方法2：两层循环两层循环枚举a,b的值，判断a+b是否存在：fora=1tondoforb=1tondoif(vis[f[a]+f[b]]=1)and(ab)thenbegininc(ans);vis[f[a]+f[b]]=2;//避免出现重复的等式end;方法2：参考代码1.vari,n,a,b,ans:longint;2.vis:array[0..20005]of0..2;3.f:array[0..105]oflongint;4.begin5.readln(n);6.fillchar(vis,sizeof(vis),0);7.fori:=1tondo8.begin9.read(f[i]);10.vis[f[i]]:=1;11.end;12.ans:=0;13.fora:=1tondo14.forb:=1tondo15.if(vis[f[a]+f[b]]=1)and(ab)then16.begin17.inc(ans);18.vis[f[a]+f[b]]:=2;19.end;20.writeln(ans);21.end.数字统计(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试题分析题目大意是给定a,b，统计a,b之间数字2出现的次数。从a到b直接枚举每一个数，判断这个数中含有几个2。fori=atobdo{求i中含2的个数t;ans=ans+t;}输出t;参考程序：1.vari,a,b,ans:longint;2.begin3.readln(a,b);4.ans:=0;5.fori:=atobdo6.begin7.ifimod10=2theninc(ans);8.ifidiv10mod10=2theninc(ans);9.ifidiv10div10mod10=2theninc(ans);10.ifidiv10div10div10mod10=2theninc(ans);11.end;12.writeln(ans);13.end.扫雷游戏(noip2015普及组第二题)扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。扫雷游戏(noip2015普及组第二题)输入样例133*??????*?输入样例223?*?*??输出样例1mine.out*102211*1输出样例2mine.out2*1*21对于100%的数据，1≤n≤100，1≤m≤100问题分析：本题也是简单的枚举类试题。我们从雷区的第一行第一列(1,1)开始，判断它周围有多少个地雷。由于本题读入的是字符，读入时需要注意：readln(n,m);fori=1tondobeginforj=1tomdoread(a[i][j]);readln;end;问题分析：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。判断如下：ifa[i][j-1]='*'theninc(s);ifa[i][j+1]='*'theninc(s);ifa[i+1][j-1]='*'theninc(s);ifa[i+1][j+1]='*'theninc(s);ifa[i+1][j]='*'theninc(s);ifa[i-1][j-1]='*'theninc(s);ifa[i-1][j+1]='*'theninc(s);ifa[i-1][j]='*'theninc(s);参考程序：1.vari,j,n,m,s:longint;2.a:array[0..105,0..105]ofchar;3.begin4.readln(n,m);5.fori:=1tondo6.begin7.forj:=1tomdoread(a[i][j]);8.readln;9.end;10.fori:=1tondo11.begin12.forj:=1tomdo13.begin14.s:=0;15.ifa[i,j]='*'thenwrite(a[i,j])16.elsebegin17.ifa[i][j-1]='*'theninc(s);18.ifa[i][j+1]='*'theninc(s);19.ifa[i+1][j-1]='*'theninc(s);20.ifa[i+1][j+1]='*'theninc(s);21.ifa[i+1][j]='*'theninc(s);22.ifa[i-1][j-1]='*'theninc(s);23.ifa[i-1][j+1]='*'theninc(s);24.ifa[i-1][j]='*'theninc(s);25.write(s);26.end;27.end;28.writeln;29.end;30.end.比例简化(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比例简化试题分析读入a,b,L后，从1到L分别枚举a’和b’。判断a’和b’是否合法，合法的话就记录下来。输入a,b,L;fori=1toLdoforj=1toLdoifi,j合法then{ansx=i;ansy=j;}输出ansx,ansy;比例简化试题分析程序的关键在于如何判断i,j合法。1.if(gcd(i,j)=1)and(i/j=a/b)then2.ifi/j-a/bminnthen3.begin4.minn:=i/j-a/b;5.ansx:=i;ansy:=j;6.end;条件1：i和j互质；条件2：i/j的值大于等于A/B的值；条件3：i/j－A/B的值尽可能小；比例简化参考程序：1.vara,b,L,i,j,ansx,ansy:longint;2.minn:real;3.