noip普及组历届试题分析.ppt

引言
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 拓扑排序)
文化之旅(2012p4 floyd算法)
一、枚举类试题
枚举法的基本思想是根据提出的问题枚举所有可能的解,并用问题给定的条件检验哪些解是需要的,哪些解是不需要的。能使条件成立,即为其解。
枚举法其实是最简单的搜索算法。
珠心算测验(noip2014普及组第一题)
珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练,既能够开发智力,又能够为日常生活带来很多便利,因而在很多学校得到普及。
某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合,集合中的数各不相同,然后要求学生回答:其中有多少个数,恰好等于集合中另外两个(不同的)数之和? 最近老师出了一些测验题,请你帮忙求出答案。
珠心算测验(noip2014普及组第一题)
【输入】
输入共两行,第一行包含一个整数n,表示测试题中给出的正整数个数。
第二行有n个正整数,每两个正整数之间用一个空格隔开,表示测试题中给出的正整数。
【输出】
输出共一行,包含一个整数,表示测验题答案。
【样例输入】【样例输出】
4 2
1 2 3 4
对于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;
for c:=1 to n do
for a:=1 to n do
for b:=1 to n do
if (f[c]=f[a]+f[b])and(c<>a)and(a<>b)and(c<>b) then
inc(ans);
writeln(ans);
样例中,上述错误答案是4:3=1+2, 3=2+1, 4=1+3, 4=3+1
方法1:参考程序
var i,n,a,b,c,t,ans:longint;
f:array[0..105]of longint;
begin
readln(n);
for i:=1 to n do read(f[i]);
ans:=0;
for c:=1 to n do
begin
t:=0;
for a:=1 to n do
for b:=1 to n do
if (f[c]=f[a]+f[b])and(t=0)and(c<>a)and(a<>b)and(c<>b) then
begin
inc(ans);
t:=1;
end;
end;
writeln(ans);
end.
方法2:两层循环
我们能不能使用两层循环呢?
由于本题测验题给出的正整数大小不超过10,000,我们可以直接枚举A,B,判断A+B在不在给定的数中即可。
定义一个数组vis,初始值为0;
读入数a[i]时,vis[a[i]]标记为1。
for i=1 to n do
{
read(f[i]); vis[f[i]]=