资源描述：
《noip普及组历届试题分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、NOIP普及组历届试题分析安徽省六安第一中学江家和引言noip复赛的知识面很广泛，对选手的综合素质考核要求更为严格，难度和分数的阶梯层次更趋科学合理，对信息学活动的推动力和社会公信力更为增强。NOIP普及组题型分布题型题目枚举扫雷游戏(2015p2)、珠心算测验(2014p1)数字统计(2010p1)、比例简化(2014p2)模拟金币(2015p1)、螺旋方阵(2014p3)、计数问题(2013p1)、寻宝(2012p2)、接水问题(2010p2)字符串数字反转(2011p1)、统计单词个数(2011p2)ISBN号码(2008p1)、乒乓球(2003p
2、1)贪心排座椅(2008p2)、纪念品分组(2007p2)NOIP普及组题型分布题型题目简单动态规划子矩阵(2014p4)、小朋友的数字(2013p3)摆花(2012p3)、导弹拦截(2010p3)道路游戏(2009p4)、传球游戏(2008p3)守望者的逃离(2007p3)、开心的金明(2006p2)采药(2005p3)、数字游戏(2003p2)数学/数论质因数分解(2012p1)、细胞分裂(2009p3)Hanoi双塔问题(2007p4)、数列(2006p4)循环(2005p4)、栈(2003p3卡特兰数)数据结构表达式求值(2013p2)、表达式的
3、值(2011p4)FBI树(2004p1)、求先序排列(2001p2)图论（提高组）车站分级(2013p4拓扑排序)文化之旅(2012p4floyd算法)一、枚举类试题枚举法的基本思想是根据提出的问题枚举所有可能的解，并用问题给定的条件检验哪些解是需要的，哪些解是不需要的。能使条件成立，即为其解。枚举法其实是最简单的搜索算法。珠心算测验(noip2014普及组第一题)珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。某学校的珠心算老师采用一种快速考察珠心算加法
4、能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？最近老师出了一些测验题，请你帮忙求出答案。珠心算测验(noip2014普及组第一题)【输入】输入共两行，第一行包含一个整数n，表示测试题中给出的正整数个数。第二行有n个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。【输出】输出共一行，包含一个整数，表示测验题答案。【样例输入】【样例输出】421234对于100%的数据，3 ≤ n ≤ 100测验题给出的正整数大小不超过10,000。试题分析题意大意：给
5、你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(c<>a)and(a<>b)and(c<>b)theninc(ans);writeln(ans);样例中，上述错误答案是4：3=1+2,3=2+1,4=1+3,4=
6、3+1方法1：参考程序vari,n,a,b,c,t,ans:longint;f:array[0..105]oflongint;beginreadln(n);fori:=1tondoread(f[i]);ans:=0;forc:=1tondobegint:=0;fora:=1tondoforb:=1tondoif(f[c]=f[a]+f[b])and(t=0)and(c<>a)and(a<>b)and(c<>b)thenbegininc(ans);t:=1;end;end;writeln(ans);end.方法2：两层循环我们能不能使用两层循环呢？由于本题
7、测验题给出的正整数大小不超过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(a<>b)thenbegininc(ans);vis[f[a]+f[b]]=2;//避免出现重复的等式end;方法2：参考代码vari,n,a,b,ans:lo
8、ngint;vis:array[0..20005]of0..2;f:array[
