《noip普与组历届试题分析》由会员分享，可在线阅读，更多相关《noip普与组历届试题分析（105页珍藏版）》请在金锄头文库上搜索。
1、NOIP普及组历届试题分析,安徽省六安第一中学 江家和,引言,noip复赛的知识面很广泛，对选手的综合素质考核要求更为严格，难度和分数的阶梯层次更趋科学合理，对信息学活动的推动力和社会公信力更为增强。,NOIP普及组题型分布,NOIP普及组题型分布,一、枚举类试题,枚举法的基本思想是根据提出的问题枚举所有可能的解，并用问题给定的条件检验哪些解是需要的，哪些解是不需要的。能使条件成立，即为其解。 枚举法其实是最简单的搜索算法。,珠心算测验 (noip2014普及组第一题),珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因
2、而在很多学校得到普及。 某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？ 最近老师出了一些测验题，请你帮忙求出答案。,珠心算测验 (noip2014普及组第一题),【输入】 输入共两行，第一行包含一个整数n，表示测试题中给出的正整数个数。 第二行有n个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。 【输出】 输出共一行，包含一个整数，表示测验题答案。 【样例输入】 【样例输出】 4 2 1 2 3 4,对于100%的数据，3 n 100 测验题
3、给出的正整数大小不超过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 (fc=fa+fb)and(ca)and(ab)and(cb) then inc(ans); writeln(ans);,样例中，上述错误
4、答案是4：3=1+2, 3=2+1, 4=1+3, 4=3+1,方法1：参考程序,var i,n,a,b,c,t,ans:longint; f:array0105of longint; begin readln(n); for i:=1 to n do read(fi); ans:=0; for c:=1 to n do begin t:=0; for a:=1 to n do for b:=1 to n do if (fc=fa+fb)and(t=0)and(ca)and(ab)and(cb) then begin inc(ans); t:=1; end; end; writeln(ans)
5、; end.,方法2：两层循环,我们能不能使用两层循环呢？,由于本题测验题给出的正整数大小不超过10,000，我们可以直接枚举A,B，判断A+B在不在给定的数中即可。,定义一个数组vis，初始值为0； 读入数ai时，visai标记为1。 for i=1 to n do read(fi); visfi=1; ,方法2：两层循环,两层循环枚举a,b的值，判断a+b是否存在： for a=1 to n do for b=1 to n do if (visfa+fb=1) and (ab) then begin inc(ans); visfa+fb=2; /避免出现重复的等式 end;,方法2：参考代
6、码,var i, n, a, b, ans:longint; vis:array020005of 02; f:array0105of longint; begin readln(n); fillchar(vis,sizeof(vis),0); for i:=1 to n do begin read(fi); visfi:=1; end; ans:=0; for a:=1 to n do for b:=1 to n do if (visfa+fb=1)and(ab) then begin inc(ans); visfa+fb:=2; end; writeln(ans); end.,数字统计 (n
7、oip2010普及组第一题),请统计某个给定范围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,试题分析,题目大意是给定a,b，统计a,b之间数字2出现的次数。 从a到b直接枚举每一个数，判断这个数中含有几个2。,for i=a to b do 求i中含2的个数t; ans=ans+
8、t; 输出t;,参考程序：,var i,a,b,ans:longint; begin readln(a,b); ans:=0; for i:=a to b do begin if i mod 10=2 then inc(ans); if i div 10 mod 10=2 then inc(ans); if i div 10 div 10 mod 10=2 then inc(ans); if i div 10 div 10 div 10 mod 10=2 then inc(ans); end; writeln(ans); end.,扫雷游戏 (noip2015普及组第二题),扫雷游戏是一款十分
9、经典的单机小游戏。 在 n 行 m 列的雷区中有一些格子含有地雷（称之为地雷格） ，其他格子不含地雷（称之为非地雷格） 。玩家翻开一个非地雷格时，该格将会出现一个数字提示周围格子中有多少个是地雷格。 游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。 现在给出n行m列的雷区中的地雷分布， 要求计算出每个非地雷格周围的地雷格数。 注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。,扫雷游戏 (noip2015普及组第二题),输入样例 1 3 3 *? ? ?*? 输入样例 2 2 3 ?*? *?,输出样例 1 mine.out *10 2
10、21 1*1 输出样例 2 mine.out 2*1 *21,对于 100%的数据，1n100，1m100,问题分析：,本题也是简单的枚举类试题。 我们从雷区的第一行第一列(1,1)开始，判断它周围有多少个地雷。 由于本题读入的是字符，读入时需要注意： readln(n,m); for i=1 to n do begin for j=1 to m do read(aij); readln; end;,问题分析：,一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。判断如下： if aij-1=* then inc(s); if aij+1=* then
11、inc(s); if ai+1j-1=* then inc(s); if ai+1j+1=* then inc(s); if ai+1j=* then inc(s); if ai-1j-1=* then inc(s); if ai-1j+1=* then inc(s); if ai-1j=* then inc(s);,参考程序：,var i,j,n,m,s:longint; a:array0105,0105of char; begin readln(n,m); for i:=1 to n do begin for j:=1 to m do read(aij); readln; end; for
12、 i:=1 to n do begin for j:=1 to m do begin s:=0; if ai,j=* then write(ai,j),else begin if aij-1=* then inc(s); if aij+1=* then inc(s); if ai+1j-1=* then inc(s); if ai+1j+1=* then inc(s); if ai+1j=* then inc(s); if ai-1j-1=* then inc(s); if ai-1j+1=* then inc(s); if ai-1j=* then inc(s); write(s); end
13、; end; writeln; end; end.,比例简化 (noip2014普及组第二题),在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某 一观点表示支持的有 1498 人，反对的有 902 人，那么赞同与反对的比例可以简单的记为1498:902。 不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 5:3，虽然与 真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。 现给出支持人数 A，反对人数 B，以及一个上限 L，请你将 A 比 B 化简
14、为 A比 B，要求在 A和 B均不大于 L 且 A和 B互质（两个整数的最大公约数是 1）的前提下，A/B A/B 且 A/B - A/B 的值尽可能小。,比例简化 (noip2014普及组第二题),输入格式 输入共一行，包含三个整数 A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。 输出格式 输出共一行，包含两个整数 A，B，中间用一个空格隔开，表示化简后的比例。 样例输入 1498 902 10 样例输出 5 3,比例简化试题分析,读入a,b,L后，从1到L分别枚举a和b。判断a和b是否合法，合法的话就记录下来。,输入a,b,L; for i=1 to L d
15、o for j=1 to L do if i,j合法 then ansx=i; ansy=j; 输出ansx, ansy;,比例简化试题分析,程序的关键在于如何判断i,j合法。,if (gcd(i,j)=1)and(i/j=a/b) then if i/j-a/bminn then begin minn:=i/j-a/b; ansx:=i; ansy:=j; end;,条件1：i和j互质；,条件2：i/j的值大于等于A/B的值 ；,条件3：i/jA/B的值尽可能小 ；,比例简化参考程序：,var a,b,L,i,j,ansx,ansy:longint; minn:real; function gcd(x,y:longint):longint; begin if y=0 then exit(x); gcd:=gcd(y,x mod y); end; begin readln(a,b,L); minn:=99999999; for i:=1 to L do for j:=1 to L do if (gcd(i,j)=1)and(i/j=a/b) then if i/j-a/bminn then begin minn:=i/j-a/b; ansx:=i; ansy:=j; end; writeln(ansx, ,ansy);
