NOIP2010普及组满分题解.doc

个人题解+代码】NOIP2010 普及组首先前两题可以说非常水，第三题也是水题第四题难度和前三题差别有点大……1．数字统计(two.pas/c/cpp)【问题描述】请统计某个给定范围[L, R]的所有整数中，数字2 出现的次数比如给定范围[2, 22]，数字2 在数2 中出现了1 次，在数12 中出现1 次，在数20 中出现1 次，在数21 中出现1 次，在数22 中出现2 次，所以数字2 在该范围内一共出现了6次 【输入】输入文件名为two.in输入共1 行，为两个正整数L 和R，之间用一个空格隔开 【输出】输出文件名为two.out输出共1 行，表示数字2 出现的次数 【输入输出样例1】two.in two.out 2 22 6  【输入输出样例2】two.in two.out 2 100 20  【数据范围】1 ≤ L ≤ R≤ 10000  直接上题解：T1：two大水题，主要有如下几种方法：1.用字符串处理2.每次用mod10取最后一位再div103.递推递推式f[i]=f[i div 10]+f[i mod 10]然后累加即可（我是用这个做的）4.分别用数学公式计算每一位上2的个数（最快，但没必要，代码也较长）……var f:array[0..10000] of longint; l,r,i,ans:longint;begin assign(input,'two.in');reset(input); assign(output,'two.out');rewrite(output); read(l,r); f[2]:=1; for i:=10 to r do f[i]:=f[i div 10]+f[i mod 10]; for i:=l to r do inc(ans,f[i]); writeln(ans); close(input);close(output);end.2．接水问题(water.pas/c/cpp)【问题描述】学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。

现在有n 名同学准备接水，他们的初始接水顺序已经确定将这些同学按接水顺序从1到n 编号，i 号同学的接水量为wi接水开始时，1 到m 号同学各占一个水龙头，并同时打开水龙头接水当其中某名同学j 完成其接水量要求wj 后，下一名排队等候接水的同学k马上接替j 同学的位置开始接水这个换人的过程是瞬间完成的，且没有任何水的浪费即j 同学第x 秒结束时完成接水，则k 同学第x+1 秒立刻开始接水若当前接水人数n’不足m，则只有n’个龙头供水，其它m?n’个龙头关闭现在给出n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒 【输入】输入文件名为water.in第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数第2 行n 个整数w1、w2、……、wn，每两个整数之间用一个空格隔开，wi 表示i 号同学的接水量 【输出】输出文件名为water.out输出只有一行，1 个整数，表示接水所需的总时间 【输入输出样例1】water.in water.out 5 3 4 4 4 1 2 1  【输入输出样例 1 说明】第1 秒，3 人接水第1 秒结束时，1、2、3 号同学每人的已接水量为1，3 号同学接完水，4 号同学接替3 号同学开始接水。

第2 秒，3 人接水第2 秒结束时，1、2 号同学每人的已接水量为2，4 号同学的已接水量为1第3 秒，3 人接水第3 秒结束时，1、2 号同学每人的已接水量为3，4 号同学的已接水量为24 号同学接完水，5 号同学接替4 号同学开始接水第4 秒，3 人接水第4 秒结束时，1、2 号同学每人的已接水量为4，5 号同学的已接水量为11、2、5 号同学接完水，即所有人完成接水总接水时间为4 秒 【输入输出样例2】water.in water.out 8 423 71 87 32 70 93 80 76 163  【数据范围】1 ≤ n ≤ 10000，1 ≤m≤ 100 且m≤ n；1 ≤ wi ≤ 100  T2：water还是水题此题其实就是纯模拟，设a[i]为第i个水龙头已经输出的水量那么每次某个人去接水量为w的水时，就是在所有a[i]中最小的一个里面加上w由此，对于每个接水的人，都重复这一过程，最后输出所有a[i]里最大的一个就是结果对于这个思路，如果每次全部扫描来求最小值，时间复杂度O(mn)，可以AC了（话说我就直接这么写了）如果你追求完美主义，可以用堆来维护a数组，每次+w相当于一个IncreaseKey，可将时间复杂度降低到O(nlogm)var a:array[1..100] of longint; n,m,i,j,min,w,ans:longint;begin assign(input,'water.in');reset(input); assign(output,'water.out');rewrite(output); read(n,m); for i:=1 to n do begin read(w); min:=1; for j:=2 to m do if a[j]ans then ans:=a[min]; end; writeln(ans); close(input);close(output);end.3．导弹拦截(missile.pas/c/cpp)【问题描述】经过11 年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。

当工作半径为0 时，则能够拦截与它位置恰好相同的导弹但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径而当天的使用代价，就是所有系统工作半径的平方和某天，雷达捕捉到敌国的导弹来袭由于该系统尚处于试验阶段，所以只有两套系统投入工作如果现在的要求是拦截所有的导弹，请计算这一天的最小使用代价 【输入】输入文件名missile.in第一行包含4 个整数x1、y1、x2、y2，每两个整数之间用一个空格隔开，表示这两套导弹拦截系统的坐标分别为(x1, y1)、(x2, y2)第二行包含1 个整数N，表示有N 颗导弹接下来N 行，每行两个整数x、y，中间用一个空格隔开，表示一颗导弹的坐标(x, y)不同导弹的坐标可能相同 【输出】输出文件名missile.out输出只有一行，包含一个整数，即当天的最小使用代价 【提示】两个点(x1, y1)、(x2, y2)之间距离的平方是(x1? x2)2+(y1?y2)2两套系统工作半径r1、r2 的平方和，是指r1、r2 分别取平方后再求和，即r12+r22 【输入输出样例1】missile.in missile.out 0 0 10 0 18 2  -3 3  10 0  【样例 1 说明】样例1 中要拦截所有导弹，在满足最小使用代价的前提下，两套系统工作半径的平方分别为18 和0。

 【输入输出样例2】missile.in missile.out 0 0 6 0 30 5  -4 -2  -2 3  4 0  6 -2  9 1   【样例2 说明】样例中的导弹拦截系统和导弹所在的位置如下图所示要拦截所有导弹，在满足最小使用代价的前提下，两套系统工作半径的平方分别为20 和10 【数据范围】对于10%的数据，N = 1对于20%的数据，1 ≤ N ≤ 2对于40%的数据，1 ≤ N ≤ 100对于70%的数据，1 ≤ N ≤ 1000对于100%的数据，1 ≤ N ≤ 100000，且所有坐标分量的绝对值都不超过1000  T3：missile此题是排序+枚举首先计算出每个点到两个系统的距离平方我们的想法是，对于第一个系统的半径进行枚举，收容尽量多的导弹于是第二个系统的半径就可以随之确定在枚举的所有状态中找一个最小值即可话题转移到实现上来，我们先对所有导弹到第一个系统距离平方进行从小到大排序，于是在我们枚举第一个系统的半径时（当然半径肯定等于某个导弹到这个系统的距离），所有排在这个“某个导弹”前面的导弹就是第一个拦截系统所要拦截的点那么理所当然，这个排在这个导弹之后的点就是系统二所要拦截的，于是第二个系统的半径就很好确定了。

于是枚举上文所说的“这个导弹”（倒着枚举比较方便），把两个系统半径平方之和取最小值，就是最终结果这段代码如下（很短，真的很短）：ans:=a[n,1];for i:=n downto 1 dobegin   if a[i,1]+r2r2 then r2:=a[i,2];end;（a[i,1]是排好序的第i个导弹距离1号系统的距离平方，r2是当前第二套系统的半径平方的值）完整程序如下：var a:Array[1..100000,1..2] of longint; x1,x2,y1,y2,x,y,n,i,r2,ans:longint;procedure fs(s,e:longint);var m,k,j:longint; ms:array[1..2] of longint;begin m:=random(e-s+1)+s;k:=s;j:=e; ms:=a[m];a[m]:=a[k]; while kms[1]) do dec(j); if k