《普及组近5年NOIP试题分析试题分析》由会员分享，可在线阅读，更多相关《普及组近5年NOIP试题分析试题分析（67页珍藏版）》请在金锄头文库上搜索。
1、普及组近5年NOIP试题分析,安徽师大附中 叶国平,NOIP2010数字统计,请统计某个给定范围L, R的所有整数中，数字2出现的次数。比如给定范围2, 22，数字2在数2中出现了1次，在数12中出现1 次，在数20中出现1 次，在数21中出现1 次，在数22 中出现2次，所以数字2在该范围内一共出现了6次。 1 L R10000。,NOIP2010数字统计,从L到R枚举每一个数i,对i进行分离数字，直接统计有多少个2 分离数字的过程 void count(int n) while (n0) if (n%10=2) ans+; n/=10; ,NOIP2010接水问题,学校里有一个水房，水房里
2、一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。 现在有n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n 编号，i 号同学的接水量为wi。接水开始时，1 到m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j 完成其接水量要求wj 后，下一名排队等候接水的同学k马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即j 同学第x 秒结束时完成接水，则k 同学第x+1 秒立刻开始接水。若当前接水人数n不足m，则只有n个龙头供水，其它mn个龙头关闭。,NOIP2010接水问题,现在给出n 名同学的接水量，按照
3、上述接水规则，问所有同学都接完水需要多少秒。 1 n 10000，1 m 100 且m n；1 wi 100。 样例输入 样例输出 8 4 163 23 71 87 32 70 93 80 76,NOIP2010接水问题,纯模拟+贪心 每次找最短的队伍排，模拟一下。,NOIP2010导弹拦截,某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为0 时，则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。而当天的使用代价，就是所有系统工作半径的平方和。 某天，雷达捕捉到敌国的导弹来袭。由于该系统尚
4、处于试验阶段，所以只有两套系统投入工作。如果现在的要求是拦截所有的导弹，请计算这一天的最小使用代价。,NOIP2010导弹拦截,第一行包含4 个整数x1、y1、x2、y2，每两个整数之间用一个空格隔开，表示这两套导弹拦截系统的坐标分别为(x1, y1)、(x2, y2)。 第二行包含1 个整数N，表示有N 颗导弹。接下来N 行，每行两个整数x、y，中间用一个空格隔开，表示一颗导弹的坐标(x, y)。不同导弹的坐标可能相同。 对于100%的数据，1 N 100000，且所有坐标分量的绝对值都不超过1000。,NOIP2010导弹拦截,样例输入 样例输出 0 0 6 0 30 5 -4 -2 -2
5、 3 4 0 6 -2 9 1,NOIP2010导弹拦截,按照到第一个点的距离排序，确定了第一个点拦截的范围，剩下来的一定是第二个点拦截，用类似后缀和统计一下，枚举断点，统计和的最小值就行了。,NOIP2010三国,输入样例 输出样例 8 1 42 24 10 29 27 12 58 77 31 8 16 26 80 6 25 3 36 11 5 33 20 17 13 15 77 9 4 50 19,NOIP2010三国,显然每个武将对应的最大默契值都无法选到，但是可以保证能选到次大的。所以就在次大的中选一个最大的作为答案咯。这样计算机肯定也得不到更大的值所以一定是可以获胜的。,NOIP20
6、10三国,NOIP2011数字反转,给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2） -1,000,000,000 N 1,000,000,000。 样例输入 样例输出 -380 -83,NOIP2011数字反转,模拟，涉及数字分离和组合，以及负数判断 程序 cinn; if(n0)/反转 ans=(ans*10)+n%10; n/=10; if(flag)ans=-ans; coutansendl;,NOIP2011统计单词数,一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定
7、单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。 现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。,NOIP2011统计单词数,样例输入 样例输出 To 2 0 to be or not to be is a question 样例输入 样例输出 To -1 Did the Ottoman Empire lose its powe
8、r at that time 1 单词长度 10。1 文章长度 1,000,000。,NOIP2011统计单词数,从测试数据的数据量来分析。文章长度为1000000，而单词长度为10。即便一位一位的匹配。运算测试也就是在10000000左右。而实际每一个单词只有匹配一次。所以，如果控制的好的话，完全可以把运算量控制在百万级别。但即便是千万的运算次数对于我们的测评来说，还是绰绰有余的。所以，在这道题目中，不用考虑 KMP 等字符串匹配算法。 当然，这道题目在测试数据中也增加了很多陷阱。如多空格分隔。前空格分隔和后空格分隔、大小写不区分、完整匹配等等。但是，最最朴素的匹配算法，倒是很简单的能够将这
9、些问题排除掉。可以说，出题人还是主要考虑考场选手的基本功底的思路。,NOIP2011瑞士轮,2*N 名编号为12N 的选手共进行R 轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。 每轮比赛的对阵安排与该轮比赛开始前的排名有关：第 1 名和第2 名、第3 名和第4名、第2K 1 名和第2K 名、 、第 2N 1 名和第2N 名，各进行一场比赛。每场比赛胜者得1 分，负者得0 分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前
10、比赛中的表现。,NOIP2011瑞士轮,现给定每个选手的初始分数及其实力值，试计算在 R 轮比赛过后，排名第Q 的选手编号是多少。我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。 1 N 100,000，1 R 50，1 Q 2N，0 s1, s2, , s2N 108，1 w1,w2, , w2N 108。 样例输入 样例输出 2 4 2 1 7 6 6 7 10 5 20 15,NOIP2011瑞士轮,NOIP2011瑞士轮,首先说，这道题目的题目类型，应该划归为模拟。按理说，只要按照题目的要求一步一步来做，就可以解决问题。但是，这道题目，在数据量上开始做了很大文章。在第一
11、次读题时，我也武断的判断这道题的难度为中等。即在考核点上，只是考核一个快排即可。但是，很快，在我写完这道题目之后，发现，竟然只能通过 4 个点。这时才开始思考，nlogn 的效率，是否可以完成这个任务数量最大为200000，log2n 大概在 17 左右，然后乘 200000 。再去乘50 。的确是 1 亿 7 千万次左右。这的确超过了，我们能够承受的速度几倍。,NOIP2011瑞士轮,将结构定义为两个有序序列的合并。也就是归并法排序上来。这就提高了很大的难度。相信不少同学在这道题目丢分也是因为忽略了这个排序方法也就是说归并两个有序序列就成为了我们在这道题目里面的重点。题目设计为奇数项和偶数项
12、进行比，结果将必有一个增加，另外一个保持不变。那么其实在这道题里面我们就可以保证增加项的序列仍然保持有序，而未增加项的序列也保持有序。那么就需要我们在每一次做完比较后，将胜者保持在奇数项和败者保留在偶数项。这样就可以把一个序列的奇数项和偶数项分别当成两个序列。将他们合并到另外一个序列中去。,NOIP2011瑞士轮,然后再将那么序列覆盖会原有序列中。这样就能够最大效果的减少计算量。所以，本道题目，需要先进行一次快排（而且不能单纯使用左侧数值当成标准值，否则有数据将快排降速到 n2 效率）。每轮结束后，都进行一次归并排序，再覆盖回原来序列（当然，也可以使用滚动数组，让两个数组来回使用，提高效率。）
13、,NOIP2012质因数分解,已知正整数n是两个不同的质数的乘积，试求出较大的那个质数。 6 n 2*109。 样例输入 样例输出 21 7,NOIP2012质因数分解,不妨设n = x * y，那么min(x，y) = n0.5，所以直接枚举1到n0.5之间的数字i，如果i | n，那么min(x，y) = i， max(x，y) = n / i。 复杂度O(n0.5),NOIP2012寻宝,藏宝楼共有N+1层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除了顶层外，藏宝楼另有N层，每层M个房间，这M个房间围成一圈并按逆时针方向依次编号为0，M-1。其中一些房间有通往上一层的楼梯，每层楼的
14、楼梯设计可能不同。每个房间里有一个指示牌，指示牌上有一个数字x，表示从这个房间开始按逆时针方向选择第x个有楼梯的房间（假定该房间的编号为k），从该房间上楼，上楼后到达上一层的k号房间。比如当前房间的指示牌上写着2，则按逆时针方向开始尝试，找到第2个有楼梯的房间，从该房间上楼。如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。,NOIP2012寻宝,第一行2个整数N和M，之间用一个空格隔开。N表示除了顶层外藏宝楼共N层楼，M表示除顶层外每层楼有M个房间。 接下来N*M行，每行两个整数，之间用一个空格隔开，每行描述一个房间内的情况，其中第(i-1)*M+j行表示第i层j-1号房间的情
15、况（i=1,2, N,j=1,2,M）。第一个整数表示该房间是否有楼梯通往上一层（0表示没有，1表示有），第二个整数表示指示牌上的数字。注意，从j号房间的楼梯爬到上一层到达的房间一定也是j号房间。 最后一行，一个整数，表示小明从藏宝楼底层的几号房间进入开始寻宝（注：房间编号从0开始）。,NOIP2012寻宝,虑按照题意模拟，每次不停的找有楼梯的房间，不难发现这样最坏情况是每层只有一个房间，这样要找1e5*1e2*1e6显然承受不了。 一个简单的想法，每次先把有楼梯的找出来，但是这样复杂度还是过高。 注意到一个事实，一层的房间并不多，当x很大的时候，大部分我们做的操作是在这层不停的转，假设这层有
16、cnt个有楼梯的房间，那么显然每走过cnt个房间，又会回到刚开始的房间，所以我们可以将x mod cnt, 这样x就小于m了。,NOIP2012摆花,小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的n种花，从1到n标号。为了在门口展出更多种花，规定第i种花不能超过ai盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。 试编程计算，一共有多少种不同的摆花方案。 0n100，0m100，0ai100,NOIP2012摆花,样例输入 样例输出 2 4 2 3 2 有2种摆花的方案，分别是(1，1，1，2)，(1，1，2，2)。括
