《NOIP普及组历届试题分析》由会员分享，可在线阅读，更多相关《NOIP普及组历届试题分析（105页珍藏版）》请在金锄头文库上搜索。
1、NOIP普及组历届试题分析安徽省六安第一中学 江家和引言noip复赛的知识面很广泛，对选手的综合素质考核要求更为严格，难度和分数的阶梯层次更趋科学合理，对信息学活动的推动力和社会公信力更为增强。NOIP普及组题型分布题型题目枚举扫雷游戏(2015p2)、珠心算测验(2014p1) 数字统计(2010p1)、比例简化(2014p2)模拟金币(2015p1)、 螺旋方阵(2014p3)、计数问题(2013p1)、 寻宝(2012p2)、接水问题(2010p2)字符串数字反转(2011p1)、统计单词个数(2011p2) ISBN号码(2008p1)、乒乓球(2003p1)贪心排座椅(2008p2)
2、、纪念品分组(2007p2)NOIP普及组题型分布题型题目简单 动态规划子矩阵(2014p4)、小朋友的数字(2013p3) 摆花(2012p3)、导弹拦截(2010p3) 道路游戏(2009p4)、传球游戏(2008p3) 守望者的逃离(2007p3)、开心的金明(2006p2) 采药(2005p3)、数字游戏(2003p2)数学/数论质因数分解(2012p1)、细胞分裂(2009p3) Hanoi双塔问题(2007p4)、数列(2006p4) 循环(2005p4) 、栈(2003p3卡特兰数)数据结构表达式求值(2013p2)、表达式的值(2011p4) FBI树(2004p1)、求先序排
3、列(2001p2)图论（提高组）车站分级(2013p4 拓扑排序) 文化之旅(2012p4 floyd算法)一、枚举类试题n枚举法的基本思想是根据提出的问题枚举所有可能的解，并用问题给定的条件检验哪些解是需要的，哪些解是不需要的。能使条件成立，即为其解。n枚举法其实是最简单的搜索算法。珠心算测验 (noip2014普及组第一题)n珠心算是一种通过在脑中模拟算盘变化来完成 快速运算的一种计算技术。珠心算训练，既能 够开发智力，又能够为日常生活带来很多便利 ，因而在很多学校得到普及。 n某学校的珠心算老师采用一种快速考察珠心算 加法能力的测验方法。他随机生成一个正整数 集合，集合中的数各不相同，然
4、后要求学生回 答：其中有多少个数，恰好等于集合中另外两 个（不同的）数之和？ 最近老师出了一些测验 题，请你帮忙求出答案。 珠心算测验 (noip2014普及组第一题)n【输入】 输入共两行，第一行包含一个整数n，表示测试 题中给出的正整数个数。 第二行有n个正整数，每两个正整数之间用一个 空格隔开，表示测试题中给出的正整数。 n【输出】 输出共一行，包含一个整数，表示测验题答案 。n【样例输入】【样例输出】4 21 2 3 4对于100%的数据，3 n 100 测验题给出的正整数大小不超过10,000。 试题分析n题意大意：给你n个数，在这n个数中，找 到满足A+B=C的C的个数，注意不是这
5、个 等式的个数。n样例中，1,2,3,4有1+2=3，1+3=4两个。n由于本题数据规模na)and(ab) then inc(ans);writeln(ans);样例中，上述错误答案是4：3=1+2, 3=2+1, 4=1+3, 4=3+1方法1：参考程序1.var i,n,a,b,c,t,ans:longint;2. f:array0.105of longint;3.begin4. readln(n);5. for i:=1 to n do read(fi);6. ans:=0;7. for c:=1 to n do8. begin9. t:=0;10. for a:=1 to n do1
6、1. for b:=1 to n do12. if (fc=fa+fb)and(t=0)and(cb)and(cb) thenbegininc(ans);visfa+fb=2; /避免出现重复的等式 end;方法2：参考代码1.var i, n, a, b, ans:longint;2. vis:array0.20005of 0.2;3. f:array0.105of longint;4.begin5. readln(n);6. fillchar(vis,sizeof(vis),0);7. for i:=1 to n do8. begin9. read(fi);10. visfi:=1;11.
7、 end;12. ans:=0;13. for a:=1 to n do14. for b:=1 to n do15. if (visfa+fb=1)and(a=a/b) then2. if i/j-a/b=a/b) then14. if i/j-a/bk then break;8. 9. t=t+1;10.11.输出s;参考程序：1.var i, j, k, s, t:longint;2.begin3. readln(k);4. i:=1; t:=1; s:=0;5. while ik then break;12. end;13. inc(t);14. end;15. writeln(s);
8、16.end.螺旋方阵 (noip2014普及组第三题)n一个n行n列的螺旋矩阵可由如下方法生成：n 从矩阵的左上角(第1行第1列)出发，初始时向 右移动；如果前方是未曾经过的格子，则继续前 进，否则右转；重复上述操作直至经过矩阵中所 有格子。根据经过顺序，在格子中依次填入 1,2,3,.，便构成了一个螺旋矩阵。n 现给出矩阵大小n以及i和j，请你求出该矩阵中 第i行第j列的数是多少。n 下图是一个n=4时的螺旋矩阵。螺旋方阵 (noip2014普及组第三题)n输入格式n输入共一行，包含三个整数 n，i，j，每两个整数 之间用一个空格隔开，分别表示矩阵大小、待求 的数所在的行号和列号。n输出格
9、式n输出共一行，包含一个整数，表示相应矩阵中第 i 行第 j 列的数。n样例输入：4 2 3n 样例输出：14n对于 50%的数据，1 n 100; 对于 100%的数据，1 n 30,000，1 i n，1 j n。 螺旋方阵试题分析n本题首先让我们想到传统的模拟，从1,1开始往数组中填充数字，但对于30000,30000的数组，直接爆零。n对于读入的n, x, y，先判断(x,y)在第几圈，再模拟圈内的数字。螺旋方阵试题分析n如：n=4, (2,2)在第2圈，(3,1)在第1圈。nn=6，(4,5)在第2圈n圈数q=min(x, y, n-x+1, n-y+1 )即目标位置到四个边界距离的
10、最小值 螺旋方阵试题分析n圈数q求出后，前q圈的数字总和很容易 求出来。n对于任何一个方阵：n第1圈有4n-4个数;n第2圈有4(n-2)-4个数；n第3圈有4(n-4)-4个数；nn第q圈有4(n-q(n-1)-4 个数螺旋方阵试题分析n前1圈有4n-4个数;n前2圈有4n-4 + 4(n-2)-4 = 2(4n-2*4)个数；n前3圈有4(n-4)-4 + 2(4n-8) = 3(4n-3*4)个数；nn前q圈有q(4n-4q)个数；螺旋方阵试题分析n目标位置(i,j)到底在当前这一圈的第几个位置 ？n如目标数26所在的位置(4,5)，在第2圈的什么 位置？n分两种情况：n1）目标数(i,
11、j)在上行或右行；n i+j-2q+1n2）目标数(i,j)在下行或左行；n 距离第一个数的距离n i+j-2q+1螺旋方阵参考程序：nvar n,i,j,q,ans:longint;nfunction min(a,b:longint):longint;n beginn if a0 do 9. begin 10. if k mod 10=x then inc(ans); 11. k:=k div 10; 12. end; 13. end; 14. writeln(ans); 15.end.寻宝 (noip2012普及组第二题)n 传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽 千辛万苦终于找到
12、传说中的这个藏宝楼，藏宝楼的门 口竖着一个木板，上面写有几个大字：寻宝说明书。 说明书的内容如下：n 藏宝楼共有 N+1 层，最上面一层是顶层，顶层有一 个房间里面藏着宝藏。除了顶层外，藏宝楼另有 N 层 ，每层 M 个房间，这 M 个房间围成一圈并按逆时针方 向依次编号为 0，M-1。其中一些房间有通往上一 层的楼梯，每层楼的楼梯设计可能不同。每个房间里 有一个指示牌，指示牌上有一个数字 x，表示从这个房 间开始按逆时针方向选择第 x 个有楼梯的房间（假定 该房间的编号为 k），从该房间上楼，上楼后到达上一 层的 k 号房间。比如当前房间的指示牌上写着 2，则按 逆时针方向开始尝试，找到第
13、2 个有楼梯的房间，从 该房间上楼。如果当前房间本身就有楼梯通向上层， 该房间作为第一个有楼梯的房间。寻宝 (noip2012普及组第二题)n 寻宝说明书的最后用红色大号字体写着：“寻宝须知：帮 助你找到每层上楼房间的指示牌上的数字（即每层第一个进 入的房间内指示牌上的数字）总和为打开宝箱的密钥”。n 请帮助小明算出这个打开宝箱的密钥。n【输入】n 第一行 2 个整数 N 和 M，之间用一个空格隔开。N 表示 除了顶层外藏宝楼共 N 层楼，M 表示除顶层外每层楼有 M 个房间。n 接下来 N*M 行，每行两个整数，之间用一个空格隔开， 每行描述一个房间内的情况，其中第(i-1)*M+j 行表示
14、第 i 层 j-1 号房间的情况（i=1, 2, , N；j=1, 2, ,M）。第一个 整数表示该房间是否有楼梯通往上一层（0 表示没有，1 表 示有），第二个整数表示指示牌上的数字。注意，从 j 号房 间的楼梯爬到上一层到达的房间一定也是 j 号房间。n 最后一行，一个整数，表示小明从藏宝楼底层的几号房间 进入开始寻宝（注：房间编号从 0 开始）。寻宝 (noip2012普及组第二题)n【输出】n输出只有一行，一个整数，表示打开宝箱的密钥 ，这个数可能会很大，请输出对 20123取模的结 果即可。n 【输入输出样例】ntreasure.in treasure.out n2 3 5n1 2
15、n0 3 n1 4 n0 1 n1 5 n1 2 n1 寻宝 (noip2012普及组第二题)n【输入输出样例说明】n第一层：n0 号房间，有楼梯通往上层，指示牌上的数字是 2；n1 号房间，无楼梯通往上层，指示牌上的数字是 3；n2 号房间，有楼梯通往上层，指示牌上的数字是 4；n第二层：n0 号房间，无楼梯通往上层，指示牌上的数字是 1；n1 号房间，有楼梯通往上层，指示牌上的数字是 5；n2 号房间，有楼梯通往上层，指示牌上的数字是 2；n小明首先进入第一层（底层）的 1 号房间，记下指示牌 上的数字为 3，然后从这个房间开始，沿逆时针方向选 择第 3 个有楼梯的房间 2 号房间进入，上楼后到达第二 层的 2 号房间，记下指示牌上的数字为 2，由于当前房 间本身有楼梯通向上层，该房间作为第一个有楼梯的房 间。因此，此时沿逆时针方向选择第 2 个有楼梯的房间 即为 1 号房间，进入后上楼梯到达顶层。这时把上述记 下的指示牌上的数字加起来，即 3+2=5，所以打开宝箱 的密钥就是 5。寻宝 试题分析n题目大意：n层楼，每层m个房间。每个 房间有一个号码，楼梯。从底楼出发，如 果该房间有楼梯
