NOIP2010普及组复赛试题分析.pptVIP

NOIP2010普及组复赛 NOIP2010普及组复赛 第1题 “数字统计”简述 （LANJS5161） 请统计某个给定范围[L, R]的所有整数中，数字2 出现的次数。 比如给定范围[2, 22]，数字2 在数2 中出现了1 次，在数12 中出现1 次，在数20 中出现1 次，在数21 中出现1 次，在数22 中出现2 次，所以数字2 在该范围内一共出现了6次。 【输入】 输入共1 行，为两个正整数L 和R，之间用一个空格隔开。 【输出】 输出共1 行，表示数字2 出现的次数。 【样例1】 two.in two.out 2 22 6 【数据范围】 1 ≤ L ≤ R≤ 10000 确定解题思路 数据范围很小，10000，直接模拟就可以了 统计“2”的个数，可以用 “mod 10”,或者字符串 例程 PASCAL (1) var l,r,s:longint; i,j:longint; st: string; begin readln(l,r); s:=0; for i:=l to r do begin str(i,st); for j:=1 to length(st) do if st[j]=2 then inc(s); end; writeln(s); end. 例程 PASCAL (2) var l,r,s:longint; i,k:longint; begin readln(l,r); s:=0; for i:=l to r do begin k:=j; while k0 do begin if k mod 10=2 then inc(s); k:=k div 10; end; end; writeln(s); end. 第2题 “接水问题”简述（LANJS5162） 题目描述很长，其实很简单： 有m个水龙头，有n 名同学排好队按顺序去接水，问所有同学都接完水至少需要多少秒 ？ 【输入格式】water.in 第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数。 第2 行n 个整数w1、w2、……、wn，每两个整数之间用一个空格隔开，wi 表示i 号同学的接水量。 【输出格式】water.out 输出只有一行，1 个整数，表示接水所需的总时间。 【输入样例1】 【输出样例1】 5 3 4 4 4 1 2 1 确定解题思路 数据范围很小，n≤10000，m≤100，直接模拟的时间复杂度：O(nm)=106 编程过程中注意减少不必要的计算 例程 PASCAL var n,m,mini,minj,i,j,max:longint; s:array[1..10000]of longint; begin readln(n,m); // 读入 for i:=1 to n do read(s[i]); for i:=m+1 to n do // 处理后面部分 begin mini:=s[1]; minj:=1; for j:=2 to m do // 找最小 if minis[j] then begin mini:=s[j]; minj:=j; end; s[minj]:=s[minj]+s[i]; // 加到最小的后面 end; max:=s[1]; for i:=2 to m do // 找最大时间 if s[i]max then max:=s[i]; writeln(max); end. 第3题 “导弹拦截”简述 （LANJS5163） 某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。系统只有两套，并且该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。而当天的使用代价，就是所有系统工作半径的平方和。 已知敌国的导弹的位置。如果现在的要求是拦截所有的导弹，请计算这一天的最小使用代价。 【输入格式】missile.in 第一行包含4 个整数x1、y1、x2、y2，每两个整数之间用一个空格隔开，表示这两套导弹拦截系统的坐标分别为(x1,