普及组近年noip试题分析报告试题分析报告

《普及组近年noip试题分析报告试题分析报告》由会员分享，可在线阅读，更多相关《普及组近年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接水问题 现在给

3、出n 名同学的接水量，按照上述接水规则，问 所有同学都接完水需要多少秒。 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导弹拦截 样例输入样

5、例输出 0 0 6 030 5 -4 -2 -2 3 4 0 6 -2 9 1 NOIP2010导弹拦截 按照到第一个点的距离排序，确定了第一个点拦截的 范围，剩下来的一定是第二个点拦截，用类似后缀和 统计一下，枚举断点，统计和的最小值就行了。 NOIP2010三国 输入样例输出样例 81 42 24 10 29 27 12 5877 31 8 16 26 80 6 25 3 36 11 5 33 20 17 13 15 77 9 4 50 19 NOIP2010三国 显然每个武将对应的最大默契值都无法选到， 但是可以保证能选到次大的。所以就在次大的 中选一个最大的作为答案咯。这样计算机肯定

6、也得不到更大的值所以一定是可以获胜的。 NOIP2010三国 12345678 142 24 10 29 27 12 58 24231816 26 806 324 3125336 115 41082533 20 17 13 529 1633315 779 627 26 36 20 15450 712 80 11 17 77419 8586513950 19 NOIP2011数字反转 给定一个整数，请将该数各个位上数字反转得 到一个新数。新数也应满足整数的常见形式， 即除非给定的原数为零，否则反转后得到的新 数的最高位数字不应为零（参见样例2） -1,000,000,000 N 1,000,00

7、0,000。 样例输入样例输出 -380-83 NOIP2011数字反转 模拟，涉及数字分离和组合，以及负数判断 程序 cinn; if(n0)/反转 ans=(ans*10)+n%10; n/=10; if(flag)ans=-ans; coutk 时 j不能排斥(把相同 文化之间也认为排斥)i，k不能排斥j和i，为什么说是 可能的距离呢，因为这样并不能准确的求出答案，比 如i-x-k-y-j， 但是 y排斥x，这样判断的时候并不 能够判断出来，还是会用i-k-j来更新i-j。但是由于 这题官方数据极弱，如果直接输出这个错误的答案能 得到90分。 NOIP2012文化之旅 剪枝1（可行性剪枝

8、）：每次经过一个点x，就把这个 所有排斥这个点x的点y标记一下，因为之后肯定不可 以经过那个点y。 剪枝2（最优性剪枝）：考虑当前在点x，已经走过距 离len，x-y有一条边，接下来我们要从x-y，那么如 果len + gxy(边x-y的长度)+distyt = ans， 那么这 个解一定不会比答案更优，为什么呢？因为之前我们 说dist是一个不准确的值，这个值是不大于真正的值 的，也就是len+gxy+真实值 = len + gxy + distyt = ans， 即len+gxy+真实值 = ans， 所以这个方案不可能比 ans更小，所以剪去。 NOIP2013计数问题 试计算在区间1到

9、n的所有整数中，数字x（0x9）共 出现了多少次？例如，在1到11中，即在1、2、3、4 、5、6、7、8、9、10、11中，数字1出现了4次。 【输入】 输入共1行，包含2个整数n、x，之间用一个空格隔开。 【输出】 输出共1行，包含一个整数，表示x出现的次数。 NOIP2013计数问题 直接暴力枚举每个数，看看有多少个x就行了。 NOIP2013表达式求值 给定一个只包含加法和乘法的算术表达式，请你编程 计算表达式的值。 输入仅有一行，为需要你计算的表达式，表达式中只 包含数字、加法运算符“+”和乘法运算符“*”，且没有 括号，所有参与运算的数字均为0到231-1之间的整 数。输入数据保证

10、这一行只有0 9、+、*这12种字符 。 输出只有一行，包含一个整数，表示这个表达式的值 。注意：当答案长度多于4位时，请只输出最后4位， 前导0不输出。 NOIP2013表达式求值 一般的方法是用栈模拟，但是本题只有+和*，于是以 每个+为分隔符算出所有数*起来的结果就行了。 NOIP2013小朋友的数字 有n个小朋友排成一列。每个小朋友手上都有一个数 字，这个数字可正可负。规定每个小朋友的特征值等 于排在他前面（包括他本人）的小朋友中连续若干个 （最少有一个）小朋友手上的数字之和的最大值。 作为这些小朋友的老师，你需要给每个小朋友一个分 数，分数是这样规定的：第一个小朋友的分数是他的 特征

11、值，其它小朋友的分数为排在他前面的所有小朋 友中（不包括他本人），小朋友分数加上其特征值的 最大值。 请计算所有小朋友分数的最大值，输出时保持最大值 的符号，将其绝对值对p取模后输出。 NOIP2013小朋友的数字 输入 p第一行包含两个正整数n、p，之间用一个空格隔开。 p第二行包含n个数，每两个整数之间用一个空格隔开，表示 每个小朋友手上的数字。 输出 p输出只有一行，包含一个整数，表示最大分数对p取模的结 果。 100%的数据，1n1,000,000，1p109，其他数字 的绝对值均不超过109。 NOIP2013小朋友的数字 输入 p第一行包含两个正整数n、p，之间用一个空格隔开。 p

12、第二行包含n个数，每两个整数之间用一个空格隔开，表示 每个小朋友手上的数字。 输出 p输出只有一行，包含一个整数，表示最大分数对p取模的结 果。 100%的数据，1n1,000,000，1p109，其他数字的 绝对值均不超过109。 NOIP2013小朋友的数字 样例输入样例输出 5 99721 1 2 3 4 5 小朋友的特征值分别为1、3、6、10、15，分数分别 为1、2、5、11、21，最大值21对997的模是21。输出 21 NOIP2013小朋友的数字 特征值其实是最大子序列，用gi表示以第i个数结尾 的最大子序列的值，那么gi=max(ai,gi-1+ai)，其 中a数组表示手上

13、的数字。那么特征值fi=max(gi,fi- 1) 对于分数，除了第一个人显然是不下降的，于是只要 用第1个和第n个比较就好。第i个的分数如果是x，显 然i+1是max(x,x+fi)也就是x+max(0,fi)，那么第n个 人的分数就是2*f1+max(fi,0)其中i是从2到n-1，注 意别爆long long就可以了 NOIP2013车站分级 一条单向的铁路线上，依次有编号为1, 2, , n的n个 火车站。每个火车站都有一个级别，最低为1级。现 有若干趟车次在这条线路上行驶，每一趟都满足如下 要求：如果这趟车次停靠了火车站x，则始发站、终 点站之间所有级别大于等于火车站x的都必须停靠。

14、 （注意：起始站和终点站自然也算作事先已知需要停 靠的站点） 例如，下表是5趟车次的运行情况。其中，前4趟车次 均满足要求，而第5趟车次由于停靠了3号火车站（2 级）却未停靠途经的6号火车站（亦为2级）而不满足 要求。 NOIP2013车站分级 NOIP2013车站分级 第一行包含2个正整数n, m，用一个空格隔开。 第i+ 1行（1 i m）中，首先是一个正整数si（2 si n），表示第i趟车次有si个停靠站；接下来有si个正整 数，表示所有停靠站的编号，从小到大排列。每两个 数之间用一个空格隔开。输入保证所有的车次都满足 要求。 输出只有一行，包含一个正整数，即n个火车站最少 划分的级别

15、数。 NOIP2013车站分级 第一行包含2个正整数n, m，用一个空格隔开。 第i+ 1行（1 i m）中，首先是一个正整数si（2 si n），表示第i趟车次有si个停靠站；接下来有si个正整 数，表示所有停靠站的编号，从小到大排列。每两个 数之间用一个空格隔开。输入保证所有的车次都满足 要求。 输出只有一行，包含一个正整数，即n个火车站最少 划分的级别数。 对于100%的数据，1 n, m 1000。 NOIP2013车站分级 样例输入样例输出 9 22 4 1 3 5 6 3 3 5 6 样例输入样例输出 9 33 4 1 3 5 6 3 3 5 6 3 1 5 9 NOIP2013车站分级 对于一班车，如果从l到r没有经过x，那么所有经过的 车站（比如y）等级都会大于x，连一条y到x的边，那 么暴力连边是O(n3)，用bitset压位就能建出来图， 这是个有向无环图，因为yx，就不可能xy。然后很 显然的贪心思想就是最外层没有入边的点是最大值， 删掉那些边，剩下的没有入边的点是次大，然后一层 一层消，直到消玩为止，这个复杂度是O(n2)。 NOIP2014珠心算测试 珠心算是一种通过在脑中模拟算盘变化来完成快速运 算的一种计算技术。珠心算训练，既能够开发智力， 又