noip2010普及组复赛解题报告.docVIP

noip2010普及组复赛解题报告 noip2010普及组复赛解题报告 解题报告 总体评价 本套题难度：★★☆☆☆ 总时间：上午：3小时，下午：1小时，讲解：1.5小时 提交次数：3 评价：前两题很水，后两题（尤其第三题）思路很绕，代码相对简单 题目分析及代码实现 第一题 数字统计，统计一个区间内‘2’出现的次数，例如：22中2出现2次 难度：★☆☆☆☆ 时间：记不清了，带上第二题一共用了大约1小时 思路：本来想将数字转换为字符串，然后再找，但是这样做有点麻烦，因为数据范围小，所以就写两重循环的。穷举区间内的数字，然后将每个数字mod 10，如果为2，计数器加1，然后div2 思考时间：10分钟左右 分数：满分 代码： program ex01; const inf=#39;two.in#39;; ouf=#39;two.out#39;; var a,b,i,j,k,tot:longint; begin assign(input,inf);reset(input); assign(output,ouf);rewrite(output); readln(a,b); tot:=0; for i:=a to b do begin k:=i; while k0 do begin if k mod 10=2 then begin tot:=tot+1;//计数器+1 k:=k div 10; end else k:=k div 10; end; end; writeln(tot); close(input);close(output); end. 第二题 接水，求n个人接水所用的最短时间 难度：★☆☆☆☆ 时间：记不清了，带上第一题一共用了大约1小时 思路：此题其实就是纯模拟，设a[i]为第i个水龙头已经输出的水量。那么每次某个人去接水量为w的水时，就是在所有a[i]中最小的一个里面加上w。由此，对于每个接水的人，都重复这一过程，最后输出所有a[i]里最大的一个就是结果。 此题数据范围小，模拟就可以过，其他方法我也想不出来 分数：满分 思考时间：5分钟左右 代码：program ex01; const inf=#39;water.in#39;; ouf=#39;water.out#39;; var n,m,i,j,k,tot,min,max:longint; a:array[1..10000] of longint; b:array[1..100] of longint; begin assign(input,inf);reset(input); assign(output,ouf);rewrite(output); readln(n,m); for i:=1 to n do a[i]:=0; for i:=1 to n do read(a[i]); for i:=1 to m do b[i]:=a[i]; min:=maxlongint; max:=-maxlongint; if n=m then//如果水管数和人数相等，那么直接输出节水量的最大值就行了 begin for i:=1 to m do if b[i]max then max:=b[i]; writeln(max); close(input);close(output); halt; end; for i:=m+1 to n do begin min:=maxlongint; for j:=1 to m do if b[j]min then begin min:=b[j]; k:=j;//找接水量最小的水管，并记录该水管的位置 end; b[k]:=b[k]+a[i];//该水管的节水量+下一个人的接水量 end; max:=-maxlongint; for i:=1 to m do if b[i]max then max:=b[i];//搜一遍，找接水量的最大值 writeln(max); close(input);close(output); end. 第三题 两个导弹，求拦截导弹的最小和半径（半径的平方和） 难度：★★★★☆ 时间：具体是一小时还是两小时记不清了 考试时的思路：贪心，求到两个圆心的最大值，然后如果该点到A的距离小于到B 的距离，则半径为该点到A的距离，另一个半径用同样的方法求结果：20分 错误点：这样求出的半径会使有些点拦截不到 正确思路：排序+穷举 求所有点到两个圆心的距离，按到A圆的距离排序，按升序，则前i个给A，后面的给B 例如：到A的距离：123 4 5 到B 的距离：2543 1 如果i=3，前3个让A拦截，r=3，后两个让B拦截，r：=3 如果i=4，前4个让A拦截，r=4，后一个让B拦截，r：=1 按照这个思路，需要排序之后穷举i