普及组近5年noip试题分析.ppt

普及组近5年NOIP试题分析
安徽师大附中叶国平
NOIP2010——数字统计
请统计某个给定范围[L, R]的所有整数中,数字2出现的次数。比如给定范围[2, 22],数字2在数2中出现了1次,在数12中出现1 次,在数20中出现1 次,在数21中出现1 次,在数22 中出现2次,所以数字2在该范围内一共出现了6次。
1≤ L ≤ R≤10000。
NOIP2010——数字统计
从L到R枚举每一个数i,对i进行分离数字,直接统计有多少个2......
分离数字的过程
void count(int n)
{while (n>0)
{if (n%10==2) ans++;
n/=10;
}
}
NOIP2010——接水问题
学校里有一个水房,水房里一共装有m 个龙头可供同学们打开水,每个龙头每秒钟的供水量相等,均为1。
现在有n 名同学准备接水,他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n 编号,i 号同学的接水量为wi。接水开始时,1 到m 号同学各占一个水龙头,并同时打开水龙头接水。当其中某名同学j 完成其接水量要求wj 后,下一名排队等候接水的同学k马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的,且没有任何水的浪费。即j 同学第x 秒结束时完成接水,则k 同学第x+1 秒立刻开始接水。若当前接水人数n’不足m,则只有n’个龙头供水,其它m−n’个龙头关闭。
NOIP2010——接水问题
现在给出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 时,则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷:每套系统每天只能设定一次工作半径。而当天的使用代价,就是所有系统工作半径的平方和。
某天,雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段,所以只有两套系统投入工作。如果现在的要求是拦截所有的导弹,请计算这一天的最小使用代价。
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 3
4 0
6 -2
9 1
NOIP2010——导弹拦截
按照到第一个点的距离排序,确定了第一个点拦截的范围,剩下来的一定是第二个点拦截,用类似后缀和统计一下,枚举断点,统计和的最小值就行了。